Submit Info #3629

Problem Lang User Status Time Memory
Static RMQ cpp (anonymous) AC 1181 ms 11.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.54 MiB
max_random_00 AC 1175 ms 11.25 MiB
max_random_01 AC 1176 ms 11.29 MiB
max_random_02 AC 1173 ms 10.96 MiB
max_random_03 AC 1181 ms 11.39 MiB
max_random_04 AC 1179 ms 11.25 MiB
random_00 AC 945 ms 10.75 MiB
random_01 AC 973 ms 10.80 MiB
random_02 AC 723 ms 3.87 MiB
random_03 AC 190 ms 8.76 MiB
random_04 AC 286 ms 9.12 MiB
small_00 AC 9 ms 0.55 MiB
small_01 AC 7 ms 0.66 MiB
small_02 AC 7 ms 0.59 MiB
small_03 AC 9 ms 0.62 MiB
small_04 AC 8 ms 0.66 MiB
small_05 AC 7 ms 0.55 MiB
small_06 AC 7 ms 0.66 MiB
small_07 AC 6 ms 0.62 MiB
small_08 AC 8 ms 0.63 MiB
small_09 AC 7 ms 0.66 MiB

#include<bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define int long long #define vec(a,n) vector<int> (a)((n)); #define Vec(a,n) vector<string> (a)((n)); #define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0)); #define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0)); #define P pair<int,int> #define All(a) (a).begin(),(a).end() #define Sort(a) sort(All(a)); #define Reverse(a) reverse(All(a)); #define PQ(n) priority_queue<P,vector<P>,greater<P>> (n) #define pq(n) priority_queue<int> (n) #define print(a) cout << (a) << endl #define printD(a) cout << setprecision(15) << (a) << endl; using namespace std; int max_int = 1000000007; void Debug(auto a); int nibul(auto a,auto b); int nibuu(auto a,auto b); void input(vector<auto>& a,int n); int n; class LazySegmentTree{ vector<int> tree,lazy; int index; int evaluation(int a,int b){ return min(a,b); } public: int size=0; LazySegmentTree(int n){ int len = 1; while(len<n)len *= 2; tree.resize(len*2-1,max_int); lazy.resize(len*2-1,0); index = len-1; size = len; } void update(int a,int x){ a += index; tree[a] = x; while(a>0){ a = (a-1)/2; tree[a] = evaluation(tree[a*2+1],tree[a*2+2]); } } int query(int a,int b){ return query(a,b,0,0,size); } int query(int a,int b,int k,int l,int r){ if(b<=l||r<=a)return max_int; if(a<=l&&r<=b)return tree[k]; int vl=query(a,b,2*k+1,l,(l+r)/2); int vr=query(a,b,2*k+2,(l+r)/2,r); return evaluation(vl,vr); } void Print() { Debug(tree); } }; class SegmentTree{ vector<int> tree; int index; int evaluation(int a,int b){ return min(a,b); } public: int size=0; SegmentTree(int n){ int len = 1; while(len<n)len *= 2; tree.resize(len*2-1,max_int); index = len-1; size = len; } void update(int a,int x){ a += index; tree[a] = x; while(a>0){ a = (a-1)/2; tree[a] = evaluation(tree[a*2+1],tree[a*2+2]); } } int query(int a,int b){ return query(a,b,0,0,size); } int query(int a,int b,int k,int l,int r){ if(b<=l||r<=a)return max_int; if(a<=l&&r<=b)return tree[k]; int vl=query(a,b,2*k+1,l,(l+r)/2); int vr=query(a,b,2*k+2,(l+r)/2,r); return evaluation(vl,vr); } void Print() { Debug(tree); } }; signed main(){ int q; cin >> n >> q; SegmentTree sg(n); REP(i,n){ int t; cin >> t; sg.update(i,t); } REP(i,q){ int l,r; cin >> l >> r; print(sg.query(l,r)); } //sg.Print(); return 0; } void Debug(auto a){ cout << "{ "; for(auto b: a){ cout << b << " "; } cout << "}" << endl; } int nibul(auto a,auto b){ int x = lower_bound(All(a),b) - a.begin(); //key以上の初めてのitr return x; } int nibuu(auto a,auto b){ int x = upper_bound(All(a),b) - a.begin(); //key以下の最後のitr return x-1; } void input(vector<auto>& a,int n){ REP(i,n){ cin >> a[i]; } }