結果

問題 No.1170 Never Want to Walk
ユーザー DriceDrice
提出日時 2020-08-14 22:44:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 2,510 bytes
コンパイル時間 479 ms
コンパイル使用メモリ 47,680 KB
実行使用メモリ 12,264 KB
最終ジャッジ日時 2023-07-31 23:19:49
合計ジャッジ時間 4,244 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,000 KB
testcase_01 AC 2 ms
5,088 KB
testcase_02 AC 2 ms
5,048 KB
testcase_03 AC 2 ms
4,944 KB
testcase_04 AC 2 ms
5,044 KB
testcase_05 AC 2 ms
5,084 KB
testcase_06 AC 2 ms
5,016 KB
testcase_07 AC 2 ms
5,000 KB
testcase_08 AC 2 ms
5,000 KB
testcase_09 AC 2 ms
5,036 KB
testcase_10 AC 2 ms
5,056 KB
testcase_11 AC 2 ms
5,036 KB
testcase_12 AC 2 ms
4,980 KB
testcase_13 AC 2 ms
5,052 KB
testcase_14 AC 2 ms
5,044 KB
testcase_15 AC 3 ms
5,036 KB
testcase_16 AC 2 ms
5,056 KB
testcase_17 AC 2 ms
5,068 KB
testcase_18 AC 2 ms
4,956 KB
testcase_19 AC 2 ms
5,100 KB
testcase_20 AC 2 ms
5,064 KB
testcase_21 AC 3 ms
5,032 KB
testcase_22 AC 2 ms
5,072 KB
testcase_23 AC 2 ms
5,088 KB
testcase_24 AC 2 ms
5,076 KB
testcase_25 AC 2 ms
5,088 KB
testcase_26 AC 3 ms
4,980 KB
testcase_27 AC 124 ms
11,568 KB
testcase_28 AC 122 ms
11,408 KB
testcase_29 AC 128 ms
12,264 KB
testcase_30 AC 126 ms
11,772 KB
testcase_31 AC 124 ms
11,660 KB
testcase_32 AC 109 ms
11,340 KB
testcase_33 AC 117 ms
11,244 KB
testcase_34 AC 113 ms
11,464 KB
testcase_35 AC 110 ms
11,396 KB
testcase_36 AC 110 ms
11,276 KB
testcase_37 AC 109 ms
11,328 KB
testcase_38 AC 114 ms
11,564 KB
権限があれば一括ダウンロードができます

ソースコード

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