結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2025-04-30 15:55:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 313 ms / 2,000 ms |
コード長 | 1,778 bytes |
コンパイル時間 | 1,953 ms |
コンパイル使用メモリ | 198,840 KB |
実行使用メモリ | 112,000 KB |
最終ジャッジ日時 | 2025-04-30 15:55:39 |
合計ジャッジ時間 | 7,787 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MX = 2e5 + 10; const int MN = 1e6 + 10; int N, A, B, arr[MX], tim = 0; vector<int> x; vector<int> adj[MN]; int cnt[MN]; void ae(int u, int v){ adj[u].push_back(v); } struct dsu{ int par[MX], sum[MX]; void init(){ for(int p = 0; p < MX; p++){ par[p] = p; sum[p] = 1; } } int f(int x){ return par[x] = par[x] == x ? x : f(par[x]); } void Join(int u, int v){ int fu = f(u), fv = f(v); if(fu == fv) return; par[fu] = fv; sum[fv] += sum[fu]; } } D; struct segtree{ int st[MX << 1]; void build(){ for(int p = MX; p < (MX << 1); p++) arr[p - MX] = st[p] = tim++; for(int p = MX - 1; p > 0; p--){ st[p] = tim++; ae(st[p], st[p << 1]); ae(st[p], st[p << 1|1]); } } void range(int l, int r, int t){ for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){ if(l & 1) ae(t, st[l++]); if(r & 1) ae(t, st[--r]); } } } S; int vis[MN]; void dfs(int u, int t){ if(vis[u]) return; vis[u] = true; if(0 <= u && u < N) D.Join(u, t); for(int nxt : adj[u]) dfs(nxt, t); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> A >> B; x.resize(N); for(int i = 0; i < N; i++) cin >> x[i]; S.build(); for(int i = 0; i < N; i++){ { int lf = lower_bound(x.begin(), x.end(), x[i] - B) - x.begin(); int rg = lower_bound(x.begin(), x.end(), x[i] - A + 1) - x.begin() - 1; if(lf <= rg) S.range(lf, rg, arr[i]); } { int lf = lower_bound(x.begin(), x.end(), x[i] + A) - x.begin(); int rg = lower_bound(x.begin(), x.end(), x[i] + B + 1) - x.begin() - 1; if(lf <= rg) S.range(lf, rg, arr[i]); } } D.init(); for(int i = 0; i < N; i++){ if(!vis[i]) dfs(i, i); } for(int i = 0; i < N; i++) cout << D.sum[D.f(i)] << '\n'; }