結果
問題 | No.1170 Never Want to Walk |
ユーザー | Drice |
提出日時 | 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 |
ソースコード
#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; }