結果
問題 | No.2077 Get Minimum Algorithm |
ユーザー |
|
提出日時 | 2022-01-20 11:57:56 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,333 ms / 3,000 ms |
コード長 | 3,021 bytes |
コンパイル時間 | 3,353 ms |
コンパイル使用メモリ | 163,656 KB |
実行使用メモリ | 26,496 KB |
最終ジャッジ日時 | 2024-12-21 17:56:53 |
合計ジャッジ時間 | 25,232 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;namespace wtree{const int MAXN = 100000 * 2;const int INF = 0x3f3f3f3f;int sz[MAXN];int* wavelet[MAXN];int* leftsum[MAXN];int lc[MAXN]; //left childint rc[MAXN]; //right childint sr[MAXN]; //start rangeint er[MAXN]; //end rangeint tp = 0;void build(int x){int s = sr[x], e = er[x], m = (s+e)>>1, N = sz[x], ls = 0;lc[x] = rc[x] = -1;leftsum[x] = (int*) malloc(sizeof(int)*(N+1));leftsum[x][0] = 0;for(int i=1; i<=N; ++i){if(wavelet[x][i] <= m) ++ls;leftsum[x][i] = ls;}if(s==e) return;lc[x] = tp; sr[tp] = er[tp] = s; sz[tp] = ls;wavelet[tp] = (int*) malloc(sizeof(int)*sz[tp]) - 1;tp++;rc[x] = tp; sr[tp] = er[tp] = e; sz[tp] = N-ls;wavelet[tp] = (int*) malloc(sizeof(int)*sz[tp]) - 1;tp++;int ind1 = 0, ind2 = 0;for(int i=1; i<=N; ++i){if(wavelet[x][i] <= m){wavelet[lc[x]][++ind1] = wavelet[x][i];er[lc[x]] = max(er[lc[x]], wavelet[x][i]);}else{wavelet[rc[x]][++ind2] = wavelet[x][i];sr[rc[x]] = min(sr[rc[x]], wavelet[x][i]);}}build(lc[x]); build(rc[x]);free(wavelet[x]+1);return;}int getKth(int s, int e, int k, int idx = 0){// cout << s << " " << e << " " << k << " " << idx << endl;if(sr[idx]==er[idx]) return sr[idx];int lcount = leftsum[idx][e]-leftsum[idx][s-1];if(k<=lcount)return getKth(leftsum[idx][s-1]+1, leftsum[idx][e], k, lc[idx]);elsereturn getKth(s-leftsum[idx][s-1], e-leftsum[idx][e], k-lcount, rc[idx]);}}using namespace wtree;int main(){ios::sync_with_stdio(false); cin.tie(0);int N; cin >> N; int* P = (int*) malloc(sizeof(int)*N)-1;sz[tp] = N; wavelet[tp] = (int*) malloc(sizeof(int)*N)-1;sr[tp] = INF; er[tp] = -INF;int *inv = (int*) malloc(sizeof(int)*N)-1;for(int i=1; i<=N; ++i){cin >> P[i]; wavelet[tp][i] = P[i]; inv[P[i]] = i;sr[tp] = min(sr[tp], P[i]); er[tp] = max(er[tp], P[i]);}build(tp++);int Q; cin >> Q; while(Q--){int x, y; cin >> x >> y;// P_{x,y} = max(P_y,(x+1th elem of P_1,P_2,...,P_y))// first check whether P_{x, inv(y)} = yif(inv[y] >= x+1 && getKth(1, inv[y], x+1) <= y) cout << inv[y] << '\n';else{// answer is not in [y, lo], but in [y, hi]int lo = max(x, inv[y]), hi = N;// cout << lo << " " << hi << endl;while(lo+1!=hi){int mi = (lo+hi)/2;if(getKth(1, mi, x+1) <= y) hi = mi;else lo = mi;}cout << hi << '\n';}}}