結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-05-19 18:39:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,024 bytes |
コンパイル時間 | 2,476 ms |
コンパイル使用メモリ | 195,692 KB |
最終ジャッジ日時 | 2025-01-10 13:12:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using V = vector<int>; #define rep(i, n) for(int i=0; i<int(n); ++i) #define all(a) a.begin(), a.end() struct UnionFind { vector<int> d; UnionFind(int n=0) : d(n, -1) {} int find(int x) { if (d[x] < 0) return x; return d[x] = find(d[x]); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -d[find(x)]; } }; int main() { int n, a, b; cin >> n >> a >> b; V x(n); rep(i, n) cin >> x[i]; UnionFind uf(n); V y(n); rep(i, n) { int l = lower_bound(all(x), x[i]+a) - x.begin(); int r = upper_bound(all(x), x[i]+b) - x.begin() - 1; if (l > r) continue; uf.unite(i, l); ++y[l]; --y[r]; } rep(i, n-1) y[i+1] += y[i]; rep(i, n-1) if (y[i] > 0) uf.unite(i, i+1); rep(i, n) cout << uf.size(i) << "\n"; return 0; }