結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2020-08-17 17:14:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 2,302 ms |
コンパイル使用メモリ | 198,772 KB |
最終ジャッジ日時 | 2025-01-13 02:39:15 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; ///////////////////////////////////////////////////////////////////////// // UNION FIND ///////////////////////////////////////////////////////////////////////// class UnionFind { private: int siz; vector<int> a; public: UnionFind(int x) : siz(x), a(x, -1) {} int root(int x) { return a[x] < 0 ? x : a[x] = root(a[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if (x == y) return false; siz--; if (a[x] > a[y]) swap(x, y); a[x] += a[y]; a[y] =x; return true; } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -a[root(x)]; } int connected_component() { return siz; } }; ///////////////////////////////////////////////////////////////////////// // END UNION FIND ///////////////////////////////////////////////////////////////////////// signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, a, b; cin >> n >> a >> b; vector<long long> v(n); for (auto& x : v) cin >> x; UnionFind uf(n); vector<int> w(n); for (int i = 0; i < n; i++) { int l = lower_bound(v.begin(), v.end(), v[i] + a) - v.begin(); int r = prev(upper_bound(v.begin(), v.end(), v[i] + b)) - v.begin(); if (l > r) continue; uf.unite(i, l); w[l]++; w[r]--; } for (int i = 1; i < n; i++) w[i] += w[i - 1]; for (int i = 0; i < n - 1; i++) if (w[i] > 0) uf.unite(i, i + 1); for (int i = 0; i < n; i++) { cout << uf.size(i) << '\n'; } return 0; }