結果
問題 | No.1170 Never Want to Walk |
ユーザー | beet |
提出日時 | 2020-08-14 22:05:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 758 ms / 2,000 ms |
コード長 | 2,761 bytes |
コンパイル時間 | 3,131 ms |
コンパイル使用メモリ | 218,416 KB |
実行使用メモリ | 179,364 KB |
最終ジャッジ日時 | 2024-04-18 21:53:56 |
合計ジャッジ時間 | 11,061 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 4 ms
5,376 KB |
testcase_14 | AC | 4 ms
5,376 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 3 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 3 ms
5,376 KB |
testcase_22 | AC | 3 ms
5,376 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 3 ms
5,376 KB |
testcase_25 | AC | 4 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 372 ms
116,284 KB |
testcase_28 | AC | 378 ms
115,392 KB |
testcase_29 | AC | 358 ms
116,200 KB |
testcase_30 | AC | 359 ms
115,060 KB |
testcase_31 | AC | 359 ms
116,064 KB |
testcase_32 | AC | 616 ms
167,748 KB |
testcase_33 | AC | 758 ms
170,068 KB |
testcase_34 | AC | 657 ms
161,704 KB |
testcase_35 | AC | 648 ms
179,364 KB |
testcase_36 | AC | 605 ms
167,600 KB |
testcase_37 | AC | 657 ms
156,148 KB |
testcase_38 | AC | 622 ms
154,312 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } struct SCC{ vector< vector<int> > G,R,T,C; vector<int> vs,used,blg; SCC(){} SCC(int n):G(n),R(n),used(n),blg(n){} void add_edge(int u,int v){ G[u].emplace_back(v); R[v].emplace_back(u); } void dfs(int v){ used[v]=1; for(int u:G[v]) if(!used[u]) dfs(u); vs.emplace_back(v); } void rdfs(int v,int k){ used[v]=1; blg[v]=k; C[k].emplace_back(v); for(int u:R[v]) if(!used[u]) rdfs(u,k); } int build(){ int n=G.size(); for(int v=0;v<n;v++) if(!used[v]) dfs(v); fill(used.begin(),used.end(),0); int k=0; for(int i=n-1;i>=0;i--){ if(!used[vs[i]]){ T.emplace_back(); C.emplace_back(); rdfs(vs[i],k++); } } for(int v=0;v<n;v++) for(int u:G[v]) if(blg[v]!=blg[u]) T[blg[v]].push_back(blg[u]); for(int i=0;i<k;i++){ sort(T[i].begin(),T[i].end()); T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end()); } return k; } int operator[](int k) const{return blg[k];} }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,a,b; cin>>n>>a>>b; auto xs=read(n); int m=1; while(m<n) m<<=1; SCC G(m+m+n); // cout<<m<<':'<<n<<endl; auto add_edge=[&](int x,int y){ if(x<m+m+n and y<m+m+n) G.add_edge(x,y); // cout<<x<<' '<<y<<endl; }; for(int i=1;i<m;i++){ add_edge(i,(i<<1)|0); add_edge(i,(i<<1)|1); } for(int i=0;i<n;i++) add_edge(m+i,m+m+i); auto add_edge_range=[&](int x,int l,int r){ for (l += m, r += m; l < r; l >>= 1, r >>= 1) { if (l & 1) add_edge(x,l), l++; if (r & 1) --r, add_edge(x,r); } }; for(int i=0;i<n;i++){ // [x - B, x - A] { int l=lower_bound(xs.begin(),xs.end(),xs[i]-b)-xs.begin(); int r=upper_bound(xs.begin(),xs.end(),xs[i]-a)-xs.begin(); add_edge_range(m+m+i,l,r); // cout<<i<<':'<<l<<' '<<r<<newl; } // [x + A, x + B] { int l=lower_bound(xs.begin(),xs.end(),xs[i]+a)-xs.begin(); int r=upper_bound(xs.begin(),xs.end(),xs[i]+b)-xs.begin(); add_edge_range(m+m+i,l,r); // cout<<i<<':'<<l<<' '<<r<<newl; } } G.build(); map<int, int> cnt; for(int i=0;i<n;i++) cnt[G[m+i]]++; for(int i=0;i<n;i++) cout<<cnt[G[m+i]]<<newl; return 0; }