結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2024-06-15 21:02:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 356 ms / 2,000 ms |
コード長 | 2,490 bytes |
コンパイル時間 | 2,101 ms |
コンパイル使用メモリ | 143,720 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2024-06-15 21:02:46 |
合計ジャッジ時間 | 9,489 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <algorithm> #include <cassert> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <tuple> #include <vector> #include <map> #include <set> #include <queue> #include <ranges> #include <iomanip> using namespace std; using ll = long long; auto range(int n) { return views::iota(0, n); } #define repeat(n) for ([[maybe_unused]] auto : range(n)) template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", "; return os << "}"; } #ifdef ONLINE_JUDGE #define dump(expr) ; #else #define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; } #endif struct UFWithWeights { vector<int> data, weights; UFWithWeights(int n) : data(n, -1), weights(n, 1) {} int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } bool find(int x, int y) { return root(x) == root(y); } void uni(int x, int y) { x = root(x); y = root(y); if (x != y) { int new_weight = weights[x] + weights[y]; if (data[x] < data[y]) swap(x, y); data[x] += data[y]; data[y] = x; weights[x] = new_weight; } } int weight(int x) { return weights[root(x)]; } }; void solve() { int n, a, b; cin >> n >> a >> b; vector<int> vs(n); for (int i : range(n)) cin >> vs[i]; int x = 0; int ia = 0, ib = 0; auto inc = [&]() { while (ia < n && vs[ia] < x + a) ia++; // vs[ia] >= x + a while (ib + 1 < n && vs[ib + 1] <= x + b) ib++; // vs[ib] <= x + b && vs[ib + 1] > x + b }; UFWithWeights uf(n); for (int i : range(n)) { x = vs[i]; int ib0 = ib; inc(); // [*, ib0] // [ia, ib] // => // [ia, ib] ia = max(ib0, ia); for (int j = ia; j < n && j <= ib; ++j) { dump(i << " -- " << j); uf.uni(i, j); } } for (int i : range(n)) { cout << uf.weight(i) << endl; } } int main() { cout << fixed << setprecision(12); solve(); }