結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2020-08-15 00:08:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 718 ms / 2,000 ms |
コード長 | 2,900 bytes |
コンパイル時間 | 2,463 ms |
コンパイル使用メモリ | 212,584 KB |
最終ジャッジ日時 | 2025-01-13 00:48:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#if loc||local #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<(n);++i) using ll = int_fast64_t; using pll = pair<ll,ll>; constexpr ll INF = 1LL<<60; constexpr ll MOD = 1e9+7; template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;} template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;} #if loc||local template<class T>void dump(T&& t){cerr<<t<<endl;} template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);} #else void dump(){} template<class T,class... Ts> void dump(T&& h, Ts&&... t){} #endif template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;} template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;} template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;} template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;} template<class T>vector<T> vec(size_t a){return vector<T>(a);} template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));} struct union_find{ size_t n; vector<int> par; size_t group; union_find(){} union_find(size_t _n):n(_n),group(_n){ par.resize(n,-1); } void reset(size_t _n){ n = _n; group = n; par.clear(); par.resize(n,-1); } int root(int k){ if(par[k]<0)return k; return par[k] = root(par[k]); } int size(int k){ k = root(k); return -par[k]; } auto operator[](int k){ return size(k); } bool unite(int a,int b){ a = root(a); b = root(b); if(a==b)return false; if(size(a)<size(b))swap(a,b); group--; par[a] += par[b]; par[b] = a; return true; } auto operator()(int a,int b){ return unite(a,b); } bool same(int a,int b){ return root(a) == root(b); } }; signed main(){ int n,a,b; cin>>n>>a>>b; vector<ll> x(n); cin>>x; union_find uni(n); vector<bool> visited(n); set<pll> st; rep(i,n)st.emplace(x[i],i); st.emplace(INF,INF); auto bfs = [&](int s){ queue<int> que; que.emplace(s); while(!que.empty()){ int cur = que.front(); que.pop(); if(visited[cur])continue; visited[cur] = 1; auto itr = st.lower_bound({x[cur]+a,-1}); while(1){ auto [xi,to] = *itr; if(xi>x[cur]+b)break; que.emplace(to); uni.unite(cur,to); itr = st.erase(itr); } itr = st.lower_bound({x[cur]-b,-1}); while(1){ auto [xi,to] = *itr; if(a>x[cur]-xi)break; que.emplace(to); uni.unite(cur,to); itr = st.erase(itr); } } }; rep(i,n)if(!visited[i])bfs(i); rep(i,n)cout<<uni.size(i)<<endl; }