結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2020-08-15 06:28:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 295 ms / 2,000 ms |
コード長 | 1,643 bytes |
コンパイル時間 | 3,354 ms |
コンパイル使用メモリ | 197,696 KB |
最終ジャッジ日時 | 2025-01-13 01:05:55 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;} template<class T>inline void out(T t){cout << t << "\n";} template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);} template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; struct UF{ vector<int>par,sz; void init(int n){ par.resize(n); sz.resize(n); for(int i=0;i<n;i++){ par[i]=i; sz[i]=1; } } int find(int x){ return x==par[x]?x:par[x]=find(par[x]); } void unite(int x,int y){ x=find(x);y=find(y); if(x==y)return; sz[x]+=sz[y]; par[y]=x; } bool same(int x,int y){ return find(x)==find(y); } int size(int x){ return sz[find(x)]; } }; signed main(){ int N, A, B; cin >> N >> A >> B; vector<int>a(N); cin >> a; UF uf; uf.init(N); vector<int>imos(N); REP(i, N) { auto l = lower_bound(ALL(a), a[i] + A) - a.begin(); auto r = upper_bound(ALL(a), a[i] + B) - a.begin() - 1; if(l > r) 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) out(uf.size(i)); }