結果
問題 | No.875 Range Mindex Query |
ユーザー | LayCurse |
提出日時 | 2019-09-21 11:51:59 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 5,304 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 217,208 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-17 15:23:51 |
合計ジャッジ時間 | 4,395 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 31 ms
6,940 KB |
testcase_12 | AC | 25 ms
6,940 KB |
testcase_13 | AC | 21 ms
6,940 KB |
testcase_14 | AC | 21 ms
6,944 KB |
testcase_15 | AC | 29 ms
6,940 KB |
testcase_16 | AC | 26 ms
6,948 KB |
testcase_17 | AC | 29 ms
6,940 KB |
testcase_18 | AC | 27 ms
6,940 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; void *wmem; char memarr[96000000]; template<class S, class T> inline S min_L(S a,T b){ return a<=b?a:b; } template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } template<class T> struct segtree_Point_Min{ int N; int logN; T *mn; int *mnind; void malloc(int maxN, int once = 0){ int i; for(i=1;i<maxN;i*=2){ ; } mn = new T[2*i]; mnind = new int[2*i]; if(once){ setN(maxN); } } void walloc(int maxN, int once = 0, void **mem = &wmem){ int i; for(i=1;i<maxN;i*=2){ ; } walloc1d(&mn, 2*i, mem); walloc1d(&mnind, 2*i, mem); if(once){ setN(maxN); } } void free(void){ delete [] mn; delete [] mnind; } T& operator[](int i){ return mn[N+i]; } void setN(int n, int zerofill = 1, int dobuild = 1){ int i; for(i=1,logN=0;i<n;i*=2,logN++){ ; } N = i; if(zerofill){ for(i=(0);i<(N);i++){ mn[N+i] = 0; } } if(dobuild){ build(); } } void build(void){ int i; for(i=(0);i<(N);i++){ mnind[N+i] = i; } for(i=N-1;i;i--){ if(mn[2*i] <= mn[2*i+1]){ mn[i] = mn[2*i]; mnind[i] = mnind[2*i]; } else{ mn[i] = mn[2*i+1]; mnind[i] = mnind[2*i+1]; } } } inline void build(int a){ while(a > 1){ a /= 2; if(mn[a*2] <= mn[a*2+1]){ mn[a] = mn[a*2]; mnind[a] = mnind[a*2]; } else{ mn[a] = mn[a*2+1]; mnind[a] = mnind[a*2+1]; } } } inline void change(int a, T val){ mn[a+N] = val; build(a+N); } inline void add(int a, T val){ mn[a+N] += val; build(a+N); } inline pair<T,int> getMin(int a, int b){ pair<T,int> res; pair<T,int> tmp; int fga = 0; int fgb = 0; a += N; b += N; while(a < b){ if(a%2){ if(fga){ res =min_L(res, make_pair(mn[a], mnind[a])); } else{ res = make_pair(mn[a], mnind[a]); fga = 1; } a++; } if(b%2){ b--; if(fgb){ tmp =min_L(make_pair(mn[b], mnind[b]), tmp); } else{ tmp = make_pair(mn[b], mnind[b]); fgb = 1; } } a /= 2; b /= 2; } if(fga==1 && fgb==0){ return res; } if(fga==0 && fgb==1){ return tmp; } if(fga==1 && fgb==1){ res =min_L(res, tmp); return res; } return res; } inline T getMinVal(int a, int b){ T res; T tmp; int fga = 0; int fgb = 0; a += N; b += N; while(a < b){ if(a%2){ if(fga){ res =min_L(res, mn[a]); } else{ res = mn[a]; fga = 1; } a++; } if(b%2){ b--; if(fgb){ tmp =min_L(mn[b], tmp); } else{ tmp = mn[b]; fgb = 1; } } a /= 2; b /= 2; } if(fga==1 && fgb==0){ return res; } if(fga==0 && fgb==1){ return tmp; } if(fga==1 && fgb==1){ res =min_L(res, tmp); return res; } return res; } inline int getMinInd(int a, int b){ return getMin(a,b).second; } } ; int N; int Q; int A[100000]; int T; int L; int R; int main(){ int KL2GvlyY, i; wmem = memarr; int k; segtree_Point_Min<int> t; rd(N); rd(Q); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){ rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1); } } t.malloc(N); t.setN(N); for(i=(0);i<(N);i++){ t[i] = A[i]; } t.build(); for(KL2GvlyY=(0);KL2GvlyY<(Q);KL2GvlyY++){ rd(T); rd(L);L += (-1); rd(R);R += (-1); if(T==1){ swap(A[L], A[R]); t.change(L,A[L]); t.change(R,A[R]); } else{ k = t.getMinInd(L, R+1); wt_L(k+1); wt_L('\n'); } } return 0; } // cLay varsion 20190921-1 // --- original code --- // int N, Q, A[1d5], T, L, R; // { // int k; // segtree_Point_Min<int> t; // rd(N,Q,(A--)(N)); // t.malloc(N); // t.setN(N); // rep(i,N) t[i] = A[i]; // t.build(); // rep(Q){ // rd(T,L--,R--); // if(T==1){ // swap(A[L], A[R]); // t.change(L,A[L]); // t.change(R,A[R]); // } else { // k = t.getMinInd(L, R+1); // wt(k+1); // } // } // }