結果
問題 | No.878 Range High-Element Query |
ユーザー | pockyny |
提出日時 | 2019-09-06 22:56:28 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 84,012 KB |
実行使用メモリ | 9,596 KB |
最終ジャッジ日時 | 2023-09-07 01:58:09 |
合計ジャッジ時間 | 4,562 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,456 KB |
testcase_01 | AC | 4 ms
7,420 KB |
testcase_02 | AC | 4 ms
7,672 KB |
testcase_03 | AC | 4 ms
7,640 KB |
testcase_04 | AC | 4 ms
7,672 KB |
testcase_05 | AC | 5 ms
7,548 KB |
testcase_06 | AC | 3 ms
7,468 KB |
testcase_07 | AC | 3 ms
7,408 KB |
testcase_08 | AC | 5 ms
7,484 KB |
testcase_09 | AC | 5 ms
7,628 KB |
testcase_10 | AC | 4 ms
7,540 KB |
testcase_11 | AC | 320 ms
9,588 KB |
testcase_12 | AC | 237 ms
8,872 KB |
testcase_13 | AC | 256 ms
8,932 KB |
testcase_14 | AC | 194 ms
8,812 KB |
testcase_15 | AC | 238 ms
8,872 KB |
testcase_16 | AC | 326 ms
9,520 KB |
testcase_17 | AC | 347 ms
9,416 KB |
testcase_18 | AC | 343 ms
9,596 KB |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <utility> using namespace std; using ll = long long; ll n,t[200010],mx = 100000000000000; void built(){ for(int i = n-1;i>0;i--){ t[i] = t[i<<1] + t[i<<1|1]; } } void update(ll p,ll a){ for(t[p+=n] = a;p>1;p >>= 1){ t[p>>1] = t[p] + t[p^1]; } } ll query(int l, int r){ ll mn = 0; for(l += n, r += n; l<r; l >>= 1,r >>= 1){ if(l&1) mn += t[l++]; if(r&1) mn += t[--r]; } return mn; } ll s[200010]; void built2(){ for(int i = n-1;i>0;i--){ s[i] = max(s[i<<1],s[i<<1|1]); } } ll query2(int l, int r){ ll mn = -1; for(l += n, r += n; l<r; l >>= 1,r >>= 1){ if(l&1) mn = max(mn,s[l++]); if(r&1) mn = max(mn,s[--r]); } return mn; } int a[100010],le[100010],ans[100010]; pair<int,int> p[100010]; pair<pair<int,int>,int> qu[100010]; int main(){ int i,q; cin >> n >> q; for(i=0;i<n;i++){ cin >> a[i]; s[i + n] = a[i]; } built2(); for(i=0;i<n;i++){ int l = 0,r = i; if(query2(0,i)<a[i]){ le[i] = 0; continue; } while(r - l>1){ int mid = (l + r)/2; if(query2(mid,i)<a[i]) r = mid; else l = mid; } le[i] = r; } for(i=0;i<n;i++){ p[i] = {le[i],i}; } sort(p,p + n); for(i=0;i<q;i++){ int x,l,r; cin >> x >> l >> r; l--; qu[i] = {{l,r},i}; } sort(qu,qu + q); int j = 0; for(i=0;i<q;i++){ int l = qu[i].first.first,r = qu[i].first.second; while(j<n && p[j].first<=l){ update(p[j].second,1); j++; } ans[qu[i].second] = query(l,r); } for(i=0;i<q;i++){ cout << ans[i] << endl; } }