CodeForces 555B Case of Fugitive：排序+贪心

This blog post is only available in Simplified Chinse.

做CF上的英文题真是不容易…… 题目链接 CodeForces 555B：Case of Fugitive

Problem

Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates $[l_i, r_i]$ , besides, $r_i < l_{i + 1}$ for $1 ≤ i ≤ n - 1$ .

To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i-th and the (i + 1)-th islads, if there are such coordinates of x and y, that $l_i ≤ x ≤ r_i$ , $l_{i + 1} ≤ y ≤ r_{i + 1}$ and $y - x = a$ .

The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.

Input

The first line contains integers n $(2 ≤ n ≤ 2·10^5)$ and m $(1 ≤ m ≤ 2·10^5)$ — the number of islands and bridges.

Next n lines each contain two integers $l_i$ and $r_i$ $(1 ≤ l_i ≤ r_i ≤ 10^{18})$ — the coordinates of the island endpoints.

The last line contains m integer numbers $a_1, a_2, ..., a_m (1 ≤ a_i ≤ 1018)$ — the lengths of the bridges that Andrewid got.

Output

If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers $b_1, b_2, ..., b_{n - 1}$ , which mean that between islands i and i + 1 there must be used a bridge number $b_i$ .

If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.

Examples

input #1

Output #1

Yes
2 3 1

Input #2

Output #2

No

Input #3

2 1
1 1
1000000000000000000 1000000000000000000
999999999999999999

Output #3

Yes
1

Note

In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

Solution

这题大概意思是，一维直线上有N个岛屿，每个岛屿有个长度（可以看成线段），每两个岛屿之间也有个距离，现在给定M条长度确定的桥，问你能不能把这些桥架在岛屿上使所有岛屿之间联通。桥两端不能在水里，只能在相邻的岛屿上。

首先我们可以发现：既然相邻两个岛屿之间都要架桥，那么我们可以提前算出相邻岛屿之间桥的长度范围： $[ L_{i+1}-R_i,R_{i+1}-L_i ]$ 。

接下来我们有个贪心的想法，首先对这些区间按 L（左端点）排序，然后让桥去选择区间（当然要对桥长度排序）——去选择满足 $L_i ≤ b_i ≤ R_i$ 的区间。如果没有合适的区间，就 continue 呗；如果有就选择。那么有多个区间可以被选择的时候选择哪个？这里我们就要用到一个贪心的想法：为了让后面的桥能选的尽量多（或者说选上的可能性尽量大），我们应该选 R 最小的区间。如果最小的 R 都比 $b_i$ 小，那么直接输出 No 了，因为我们对 $b_I$ 排过序，之后只会越来越大，永远大于这个 R，这个区间就永远没人要了……

具体实现可以用集合，也可以用优先队列。最后就是输出答案的处理注意一下就可以了。复杂度 $\Theta (N\log_2 N)$ 。

Code

以下是我的 AC 代码（逃……

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=200005;
int n,m,cnt=0;
long long ln[maxn],rn[maxn];
struct IslandData{
    long long L,R;
    int id;
    bool operator <(const IslandData b)const{
        return R>b.R;
    }
}isd[maxn];
struct BridgeData{
    long long x;
    int id;
    bool operator <(const BridgeData b)const{
        return x<b.x;
    }
}a[maxn];
struct Answer{
    int id,x;
}ans[maxn];
priority_queue <IslandData> heap;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline long long llread(){
    long long ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=(long long)-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=(long long)ret*(long long)10+(long long)(ch-'0'),ch=getchar();
    return (long long)ret*f;
}
inline bool cmp(IslandData aa,IslandData bb){
    return aa.L<bb.L;
}
inline bool cmp_id(Answer aa,Answer bb){
    return aa.id<bb.id;
}
int main(){
    n=read();m=read();
    for (int i=1;i<=n;i++) ln[i]=llread(),rn[i]=llread();
    for (int i=1;i<n;i++){
        IslandData now;
        now.L=ln[i+1]-rn[i];
        now.R=rn[i+1]-ln[i];
        now.id=i;
        isd[i]=now;
    }
    for (int i=1;i<=m;i++) a[i].x=llread(),a[i].id=i;
    sort(a+1,a+1+m);
    sort(isd+1,isd+n,cmp);
    int j=1;
    for (int i=1;i<=m;i++){
        while (j<n&&isd[j].L<=a[i].x&&a[i].x<=isd[j].R) heap.push(isd[j++]);
        if (heap.size()==0) continue;
        IslandData now=heap.top();heap.pop();
        if (now.R<a[i].x){
            printf("No\n");
            return 0;
        }
        ans[++cnt].id=now.id;ans[cnt].x=a[i].id;
    }
    if (cnt<n-1){printf("No\n");return 0;}
    printf("Yes\n");
    sort(ans+1,ans+1+cnt,cmp_id);
    for (int i=1;i<=cnt;i++) printf("%d ",ans[i].x);
    printf("\n");
    return 0;
}

Reference

有道划词翻译Chrome插件，强烈推荐！

555B – Case of Fugitive (Codeforces) | ASDF Coding Codeforces Round #310 (Div. 1) B. Case of Fugitive - 程序园

7/9/2018