結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 22:11:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 2,497 bytes |
コンパイル時間 | 1,314 ms |
コンパイル使用メモリ | 109,332 KB |
実行使用メモリ | 12,924 KB |
最終ジャッジ日時 | 2024-10-10 15:29:45 |
合計ジャッジ時間 | 5,003 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} class DisjointSet{ public: vector<int> rank,p; vector<int> sz; DisjointSet(){} DisjointSet(int size){ rank.resize(size,0); p.resize(size,0); sz.resize(size,0); for(int i=0;i<size;i++) makeSet(i); } void makeSet(int x){ p[x]=x; rank[x]=0; sz[x]=1; } bool same(int x,int y){ return findSet(x)==findSet(y); } void unite(int x,int y){ if(same(x,y)) return; link(findSet(x),findSet(y)); } void link(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; sz[x]+=sz[y]; }else{ p[x]=y; sz[y]+=sz[x]; if(rank[x]==rank[y]){ rank[y]++; } } } int findSet(int x){ if(x!=p[x]){ p[x]=findSet(p[x]); } return p[x]; } int findSize(int x){ return sz[findSet(x)]; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; ll A,B; cin>>N>>A>>B; vector<ll> X(N); rep(i,N) cin>>X[i]; DisjointSet us(N); vector<pair<int,int>> qry; for(int i=0;i<N;i++){ {//[l,r] int l=lower_bound(all(X),X[i]-B)-X.begin(); int r=upper_bound(all(X),X[i]-A)-X.begin(); r--; if(l<=r){ us.unite(i,l); us.unite(i,r); if(l<r) qry.push_back(mkp(l,r)); } } {//[l,r] int l=lower_bound(all(X),X[i]+A)-X.begin(); int r=upper_bound(all(X),X[i]+B)-X.begin(); r--; if(l<=r){ us.unite(i,l); us.unite(i,r); if(l<r) qry.push_back(mkp(l,r)); } } } int Q=qry.size(); vector<int> ord(Q); rep(i,Q) ord[i]=i; sort(all(ord),[&](int a,int b){ if(qry[a].second==qry[b].second) return a<b; else return qry[a].second<qry[b].second; }); vector<int> left(N,0); rep(i,N) left[i]=i-1; for(auto i:ord){ int a=qry[i].first; int b=qry[i].second; int pos=b; while(left[pos]>=a&&pos>=0){ us.unite(b,pos); chmin(left[pos],left[left[a]]); pos=left[pos]; } } rep(i,N) cout<<us.findSize(i)<<"\n"; return 0; }