結果
問題 | No.878 Range High-Element Query |
ユーザー | beet |
提出日時 | 2019-09-03 17:25:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 2,837 ms |
コンパイル使用メモリ | 204,956 KB |
実行使用メモリ | 12,808 KB |
最終ジャッジ日時 | 2023-08-26 00:23:31 |
合計ジャッジ時間 | 3,674 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 64 ms
11,168 KB |
testcase_12 | AC | 49 ms
11,664 KB |
testcase_13 | AC | 48 ms
9,144 KB |
testcase_14 | AC | 36 ms
8,048 KB |
testcase_15 | AC | 50 ms
11,292 KB |
testcase_16 | AC | 65 ms
12,440 KB |
testcase_17 | AC | 68 ms
12,720 KB |
testcase_18 | AC | 72 ms
12,808 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; 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;} struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(){}; SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } }; //INSERT ABOVE HERE signed main(){ int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i],as[i]--; auto f=[](int a,int b){return min(a,b);}; SegmentTree<int> seg(f,n); seg.build(vector<int>(n,n)); vector<int> bs(n); for(int i=n-1;i>=0;i--){ bs[i]=seg.query(as[i],n); if(bs[i]<0) bs[i]=n; seg.set_val(as[i],i); } const int LOG=20; vector< vector<int> > dp(LOG,vector<int>(n+1,n)); for(int i=0;i<n;i++) dp[0][i]=bs[i]; for(int k=1;k<LOG;k++) for(int i=0;i<n;i++) dp[k][i]=dp[k-1][dp[k-1][i]]; for(int i=0;i<q;i++){ int t; cin>>t; assert(t==1); { int l,r; cin>>l>>r; l--; int num=1,pos=l; for(int k=LOG-1;k>=0;k--) if(dp[k][pos]<r) num+=1<<k,pos=dp[k][pos]; cout<<num<<"\n"; } } cout<<flush; return 0; }