結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2024-11-15 14:59:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 411 ms / 2,000 ms |
コード長 | 953 bytes |
コンパイル時間 | 2,731 ms |
コンパイル使用メモリ | 258,084 KB |
実行使用メモリ | 14,336 KB |
最終ジャッジ日時 | 2024-11-15 14:59:19 |
合計ジャッジ時間 | 9,285 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#ifndef LOCAL #include <bits/stdc++.h> using namespace std; #define debug(...) (void(0)) #else #include "algo/debug.h" #endif #include <atcoder/dsu> void solve() { int N, A, B; cin >> N >> A >> B; vector<int> X(N); for(int i = 0; i < N; i++) cin >> X[i]; atcoder::dsu uf(N); set<int> st; for(int i = 0; i <= N; i++) st.insert(i); int l = 0, r = 0; for(int i = 0; i < N; i++) { while(l < N && X[l] - X[i] < A) l++; while(r < N && X[r] - X[i] <= B) r++; for(int j = l; j < r;) { if(j < N) { st.erase(j); uf.merge(i, j); } j = *st.lower_bound(j); } st.insert(l); st.insert(r); } for(int i = 0; i < N; i++) cout << uf.size(i) << endl; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int tt = 1; // std::cin >> tt; while (tt--) { solve(); } }