結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2020-08-15 00:36:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 413 ms / 2,000 ms |
コード長 | 1,436 bytes |
コンパイル時間 | 2,200 ms |
コンパイル使用メモリ | 196,068 KB |
最終ジャッジ日時 | 2025-01-13 00:49:52 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define ALL(v) (v).begin(), (v).end() using ll = long long; constexpr int INF = 1e9; constexpr long long LINF = 1e18; constexpr long long MOD = 1e9 + 7; struct UnionFind { vector<int> par, siz; UnionFind(int n) : par(n), siz(n, 1) { iota(par.begin(), par.end(), 0); } int root(int x) { if (par[x] == x) return x; else return par[x] = root(par[x]); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) return; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return siz[root(x)]; } }; signed main() { int n; ll a, b; cin >> n >> a >> b; ll x[n]; rep(i, n) { cin >> x[i]; } UnionFind uf(n); int imos[n + 1] = {}; rep(i, n) { int l = lower_bound(x, x + n, x[i] + a) - x; int r = upper_bound(x, x + n, x[i] + b) - x - 1; if (r < l) continue; uf.unite(i, l); imos[l]++; imos[r]--; } rep(i, n - 1) { imos[i + 1] += imos[i]; } rep(i, n - 1) { if (imos[i] > 0) uf.unite(i, i + 1); } rep(i, n) { cout << uf.size(i) << endl; } return 0; }