結果

問題 No.1170 Never Want to Walk
ユーザー Drice
提出日時 2020-08-14 22:44:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 2,510 bytes
コンパイル時間 779 ms
コンパイル使用メモリ 48,904 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-10-10 16:06:41
合計ジャッジ時間 4,136 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<algorithm>
struct Segment{
    long long l,r;
    Segment(){}
    Segment(long long l,long long r):l(l),r(r){}
};
Segment seg[400005];
long long x[200005];
int f[200005];
int cnt[200005];

int find(int u){
    if(f[u]==u) return u;
    else return f[u] = find(f[u]);
}

void doMerge(int n,int m){
    int size = 0;
    int p = 1;
    while(p<=n){
        long long right = seg[p].r;
        int np = p;
        while(np+1<=n && seg[np+1].l<=right){
            np++;
            if(seg[np].r>right) right = seg[np].r;
        }
        //printf("l = %lld, r = %lld\n",seg[p].l,right);
        seg[++size] = Segment(seg[p].l,right);
        p = np+1;
    }
    for(int i = 1; i <= m; i++) f[i] = i;
    for(int i = 1; i <= size; i++){
        long long L = seg[i].l, R = seg[i].r;
        int root = R;
        for(int i = L; i <= R; i++){
            f[find(i)] = find(root);
        }
    }
}

int getUpper(long long u,int n){
    int L = 1, R = n;
    int res = -1;
    while(L<=R){
        int M = (L+R)/2;
        if(x[M]<=u){
            res = M;
            L = M+1;
        }
        else R = M-1;
    }
    return res;
}

int getLower(long long u,int n){
    int L = 1, R = n;
    int res = -1;
    while(L<=R){
        int M = (L+R)/2;
        if(x[M]>=u){
            res = M;
            R = M-1;
        }
        else L = M+1;
    }
    return res;
}

int main(){
    int n; long long a,b;
    scanf("%d%lld%lld",&n,&a,&b);
    for(int i = 1; i <= n; i++) scanf("%lld",&x[i]);
    int size = 0;
    for(int i = 1; i <= n; i++){
        int l = getLower(x[i]-b,n), r = getUpper(x[i]-a,n);
        if(l!=-1 && r!=-1) seg[++size] = Segment(l,r);
        l = getLower(x[i]+a,n), r = getUpper(x[i]+b,n);
        if(l!=-1 && r!=-1) seg[++size] = Segment(l,r);
    }
    //for(int i = 1; i <= size; i++) printf("%lld, %lld\n",seg[i].l,seg[i].r);
    std::sort(seg+1,seg+1+size,[&](Segment& u,Segment& v){ return u.l<v.l; });
    doMerge(size,n);
    for(int i = 1; i <= n; i++){
        long long down = x[i]-a;
        int id = getUpper(down,n);
        if(id!=-1 && x[id]>=x[i]-b){
            f[find(id)] = find(i);
        }
        long long up = x[i]+a;
        id = getLower(up,n);
        if(id!=-1 && x[id]<=x[i]+b){
            f[find(id)] = find(i);
        }
    }
    for(int i = 1; i <= n; i++) cnt[find(i)]++;
    //for(int i = 1; i <= n; i++) printf("find[%d] = %d\n",i,find(i));
    for(int i = 1; i <= n; i++) printf("%d\n",cnt[find(i)]);
    
    return 0;
}
0