結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2024-06-20 00:31:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 1,306 bytes |
コンパイル時間 | 3,352 ms |
コンパイル使用メモリ | 258,412 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-06-20 00:32:00 |
合計ジャッジ時間 | 7,654 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct RangeUnionFind { vector<int> data, L, R; RangeUnionFind(int N): data(N, -1), L(N), R(N) { iota(L.begin(), L.end(), 0); iota(R.begin(), R.end(), 1); } int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); } int unite(int x, int y) { if((x = find(x)) == (y = find(y))) { return false; } if(data[x] > data[y]) { swap(x, y); } data[x] += data[y]; data[y] = x; L[x] = min(L[x], L[y]); R[x] = max(R[x], R[y]); return true; } void range_unite(int l, int r) { // unite [l, r) if((l = max(l, 0)) >= (r = min(r, (int)data.size()))) { return; } int m; while((m = R[find(l)]) < r) { unite(l, m); } } int size(int k) { return -data[find(k)]; } int same(int x, int y) { return find(x) == find(y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, A, B; cin >> N >> A >> B; vector<ll> x(N); for(auto &i : x) { cin >> i; } RangeUnionFind u(N); for(ll i = 0; i < N; i++) { ll l = ranges::lower_bound(x, x[i] + A) - x.begin(), r = ranges::lower_bound(x, x[i] + B + 1) - x.begin(); if(l == r) { continue; } u.range_unite(l, r); u.unite(i, l); } for(ll i = 0; i < N; i++) { cout << u.size(i) << "\n"; } }