結果
問題 | No.1170 Never Want to Walk |
ユーザー |
![]() |
提出日時 | 2020-08-14 22:08:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 317 ms / 2,000 ms |
コード長 | 4,188 bytes |
コンパイル時間 | 2,642 ms |
コンパイル使用メモリ | 217,296 KB |
最終ジャッジ日時 | 2025-01-12 23:56:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#ifdef LOCAL //#define _GLIBCXX_DEBUG #endif //#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef pair<int, int> Pi; typedef vector<ll> Vec; typedef vector<int> Vi; typedef vector<string> Vs; typedef vector<char> Vc; typedef vector<P> VP; typedef vector<vector<ll>> VV; typedef vector<vector<int>> VVi; typedef vector<vector<char>> VVc; typedef vector<vector<vector<ll>>> VVV; typedef vector<vector<vector<vector<ll>>>> VVVV; #define REP(i, a, b) for(ll i=(a); i<(b); i++) #define PER(i, a, b) for(ll i=(a); i>=(b); i--) #define rep(i, n) REP(i, 0, n) #define per(i, n) PER(i, n, 0) const ll INF=1e18+18; const ll MOD=1000000007; #define Yes(n) cout << ((n) ? "Yes" : "No") << endl; #define YES(n) cout << ((n) ? "YES" : "NO") << endl; #define ALL(v) v.begin(), v.end() #define rALL(v) v.rbegin(), v.rend() #define pb(x) push_back(x) #define mp(a, b) make_pair(a,b) #define Each(a,b) for(auto &a :b) #define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i) #ifdef LOCAL #define dbg(x_) cerr << #x_ << ":" << x_ << endl; #define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;} #define dbgset(st) cerr << #st << ":"<<endl; for (auto i = st.begin(); i != st.end(); ++i) { cerr << *i <<" ";}cerr<<endl; #define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;} #define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl; #else #define dbg(...) #define dbgmap(...) #define dbgset(...) #define dbgarr(...) #define dbgdp(...) #endif #define out(a) cout<<a<<endl #define out2(a,b) cout<<a<<" "<<b<<endl #define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl #define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end()) #define fi first #define se second template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<typename T1, typename T2> ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; } template<typename T>istream& operator>>(istream&i,vector<T>&v) {rep(j,v.size())i>>v[j];return i;} // vector template<typename T> ostream &operator<<(ostream &s, const vector<T> &v) { int len=v.size(); for(int i=0; i<len; ++i) { s<<v[i]; if(i<len-1) s<<" "; } return s; } // 2 dimentional vector template<typename T> ostream &operator<<(ostream &s, const vector<vector<T> > &vv) { int len=vv.size(); for(int i=0; i<len; ++i) { s<<vv[i]<<endl; } return s; } //UnionFind struct UnionFind { vector<ll> par; UnionFind(ll n) : par(n, -1) { } void init(ll n) { par.assign(n, -1); } ll root(ll x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool issame(ll x, ll y) { return root(x) == root(y); } bool unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; return true; } ll size(ll x) { return -par[root(x)]; } }; int solve(){ ll n,a,b; cin>>n>>a>>b; Vec v(n); cin>>v; dbg(v); UnionFind uf(n); ll prev = -1; rep(i,n){ ll st = v[i]+a; ll ed = v[i]+b; ll sid = lower_bound(ALL(v),st) - v.begin(); ll eid = lower_bound(ALL(v),ed+1) - v.begin(); eid--; ll L = max(prev, sid); ll R = eid; if(L >= n)continue; if(L > R) continue; dbg ( mp(i,mp(sid,eid)) ); dbg ( mp(i,mp(L,R)) ); REP(j, L, R+1){ uf.unite(i,j); } // prev = R; } rep(i,n){ out(uf.size(i)); } return 0; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout<<std::setprecision(10); // ll T; // cin>>T; // while(T--) solve(); }