結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 22:12:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 2,490 bytes |
コンパイル時間 | 1,376 ms |
コンパイル使用メモリ | 131,600 KB |
最終ジャッジ日時 | 2025-01-13 00:01:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
/* Code for problem C by cookiedoth Generated 14 Aug 2020 at 04.04 PM ▅███████ ]▄▄▄▄▄▄▄ █████████▅▄▃ Il████████████████] ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤ o_O -_- ~_^ */ #include <iostream> #include <fstream> #include <vector> #include <set> #include <map> #include <bitset> #include <algorithm> #include <iomanip> #include <cmath> #include <ctime> #include <functional> #include <unordered_set> #include <unordered_map> #include <string> #include <queue> #include <deque> #include <stack> #include <complex> #include <cassert> #include <random> #include <cstring> #include <numeric> #define ll long long #define ld long double #define null NULL #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define debug(a) cerr << #a << " = " << a << endl #define forn(i, n) for (int i = 0; i < n; ++i) using namespace std; template<class T> int chkmax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; } template<class T> int chkmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; } template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) { while (begin != end) { out << (*begin) << " "; begin++; } out << endl; } template<class T> void output(T x, ostream& out = cerr) { output(x.begin(), x.end(), out); } void fast_io() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const int mx = 2e5 + 228; int n, a, b, x[mx], par[mx], sz[mx]; set<int> not_joined; int get_root(int v) { return (par[v] == v ? v : par[v] = get_root(par[v])); } void join(int u, int v) { u = get_root(u); v = get_root(v); if (u != v) { par[u] = v; sz[v] += sz[u]; } } void read() { cin >> n >> a >> b; for (int i = 0; i < n; ++i) { cin >> x[i]; } iota(par, par + n, 0); fill(sz, sz + n, 1); for (int i = 0; i < n - 1; ++i) { not_joined.insert(i); } } void process() { for (int i = 0; i < n; ++i) { int L = lower_bound(x, x + n, x[i] - b) - x; int R = upper_bound(x, x + n, x[i] - a) - x; if (R > L) { join(i, L); while (true) { auto it = not_joined.lower_bound(L); if (it == not_joined.end() || (*it) >= R - 1) { break; } else { join(*it, (*it) + 1); not_joined.erase(it); } } } } } void print_ans() { for (int i = 0; i < n; ++i) { cout << sz[get_root(i)] << '\n'; } } signed main() { fast_io(); read(); process(); print_ans(); }