結果
問題 | No.1170 Never Want to Walk |
ユーザー | 沙耶花 |
提出日時 | 2020-08-14 21:42:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 2,721 bytes |
コンパイル時間 | 3,870 ms |
コンパイル使用メモリ | 211,644 KB |
実行使用メモリ | 11,784 KB |
最終ジャッジ日時 | 2023-07-31 21:43:33 |
合計ジャッジ時間 | 9,749 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,384 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 3 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,384 KB |
testcase_14 | AC | 4 ms
4,380 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 3 ms
4,376 KB |
testcase_17 | AC | 3 ms
4,380 KB |
testcase_18 | AC | 4 ms
4,380 KB |
testcase_19 | AC | 3 ms
4,376 KB |
testcase_20 | AC | 4 ms
4,376 KB |
testcase_21 | AC | 3 ms
4,380 KB |
testcase_22 | AC | 3 ms
4,376 KB |
testcase_23 | AC | 4 ms
4,376 KB |
testcase_24 | AC | 3 ms
4,376 KB |
testcase_25 | AC | 3 ms
4,376 KB |
testcase_26 | AC | 3 ms
4,380 KB |
testcase_27 | AC | 408 ms
10,544 KB |
testcase_28 | AC | 400 ms
10,464 KB |
testcase_29 | AC | 413 ms
10,396 KB |
testcase_30 | AC | 412 ms
10,400 KB |
testcase_31 | AC | 394 ms
10,424 KB |
testcase_32 | AC | 416 ms
11,688 KB |
testcase_33 | AC | 436 ms
11,652 KB |
testcase_34 | AC | 429 ms
11,776 KB |
testcase_35 | AC | 421 ms
11,776 KB |
testcase_36 | AC | 411 ms
11,508 KB |
testcase_37 | AC | 416 ms
11,676 KB |
testcase_38 | AC | 431 ms
11,784 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 10000000 template <typename T,typename F> struct segtree{ F func; vector<T> v; int n; T init_value; segtree(int sz,F f,T iv):func(f){ init_value = iv; n=1; while(true){ if(n>=sz)break; n*=2; } v.resize(2*n,init_value); for(int i=n-1;i>=0;i--){ v[i]=func(v[i<<1],v[(i<<1)+1]); } } segtree(vector<T> &x,F f,T iv):func(f){ init_value = iv; n=1; while(true){ if(n>=x.size())break; n*=2; } v.resize(2*n,init_value); for(int i=0;i<x.size();i++){ v[n+i]=x[i]; } for(int i=n-1;i>=0;i--){ v[i]=func(v[i<<1],v[(i<<1)+1]); } } void update(int x,T val){ x+=n; v[x]=val; while(x>0){ x>>=1; v[x]=func(v[x<<1],v[(x<<1)+1]); } } T query(int l,int r){ if(l>=r)return init_value; l+=n; r+=n; T res1 = init_value; T res2 = init_value; while(true){ if(l&1){ res1=func(res1,v[l++]); } if(r&1){ res2=func(v[--r],res2); } if(l>=r)break; l>>=1;r>>=1; } return func(res1,res2); } void show(){ int n = 1; for(int i=1;i<v.size();i++){ for(int j=0;j<n;j++){ if(j!=0)cout<<' '; cout<<v[i+j]; } cout<<endl; i+=n-1; n*=2; } } }; int main(){ int N,A,B; cin>>N>>A>>B; vector<int> x(N); for(int i=0;i<N;i++)cin>>x[i]; vector<int> ans(N); auto f = [](pair<int,int> a,pair<int,int> b){ return min(a,b); }; vector<pair<int,int>> P(N); for(int i=0;i<N;i++){ P[i].first=0; P[i].second=i; } segtree<pair<int,int>,decltype(f)> seg(P,f,{1,0}); for(int i=0;i<N;i++){ if(seg.query(i,i+1).first==1)continue; seg.update(i,make_pair(1,i)); vector<int> inds; inds.push_back(i); queue<int> Q; Q.push(i); while(Q.size()!=0){ int u = Q.front(); Q.pop(); int l = distance(x.begin(),lower_bound(x.begin(),x.end(),x[u]+A)); int r = distance(x.begin(),lower_bound(x.begin(),x.end(),x[u]+B+1)); //cout<<u<<' '<<l<<' '<<r<<endl; while(true){ pair<int,int> p = seg.query(l,r); if(p.first==1)break; seg.update(p.second,make_pair(1,p.second)); Q.push(p.second); inds.push_back(p.second); } l = distance(x.begin(),lower_bound(x.begin(),x.end(),x[u]-B)); r = distance(x.begin(),lower_bound(x.begin(),x.end(),x[u]-A+1)); // cout<<u<<' '<<l<<' '<<r<<endl; while(true){ pair<int,int> p = seg.query(l,r); if(p.first==1)break; seg.update(p.second,make_pair(1,p.second)); Q.push(p.second); inds.push_back(p.second); } } for(int j=0;j<inds.size();j++)ans[inds[j]]=inds.size(); } for(int i=0;i<N;i++)cout<<ans[i]<<endl; return 0; }