Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3642

Problem Lang User Status Time Memory
Static RMQ cpp (anonymous) AC 972 ms 11.13 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.59 MiB
max_random_00 AC 972 ms 11.01 MiB
max_random_01 AC 960 ms 11.00 MiB
max_random_02 AC 965 ms 10.76 MiB
max_random_03 AC 952 ms 11.13 MiB
max_random_04 AC 964 ms 11.00 MiB
random_00 AC 805 ms 9.88 MiB
random_01 AC 797 ms 9.96 MiB
random_02 AC 614 ms 6.38 MiB
random_03 AC 165 ms 4.91 MiB
random_04 AC 242 ms 5.93 MiB
small_00 AC 7 ms 0.67 MiB
small_01 AC 7 ms 0.62 MiB
small_02 AC 7 ms 0.67 MiB
small_03 AC 8 ms 0.62 MiB
small_04 AC 7 ms 0.67 MiB
small_05 AC 7 ms 0.63 MiB
small_06 AC 8 ms 0.66 MiB
small_07 AC 7 ms 0.67 MiB
small_08 AC 8 ms 0.62 MiB
small_09 AC 8 ms 0.67 MiB

#include<iostream> #include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<string> #include<map> #include<string.h> #include<complex> #include<math.h> #include<queue> #include<time.h> using namespace std; typedef long long int llint; typedef pair<int, int> pint; typedef pair<llint, llint> pllint; typedef vector<int> vint; typedef vector<llint> vllint; typedef vector<pint> vpint; typedef vector<string> vstring; typedef vector<pair<llint, llint>> vpllint; typedef vector<vector<int>> vvint; typedef vector<vector<llint>> vvllint; typedef vector<vector<pint>> vvpint; typedef vector<bool> vbool; #define rep(i,n) for(int i=0;i<n;i++) #define drep(i,n) for(int i=n-1;0<=i;i--) #define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl; #define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl; #define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl; #define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl; #define Pi 3.1415926535897932384626 #define mod llint(1e9+7) #define Inf 2147483647 class UnionFind { public: //親の番号を格納する。親だった場合は-(その集合のサイズ) vector<int> Parent; //作るときはParentの値を全て-1にする //こうすると全てバラバラになる UnionFind(int N) { Parent = vector<int>(N, -1); } //Aがどのグループに属しているか調べる int root(int A) { if (Parent[A] < 0) return A; return Parent[A] = root(Parent[A]); } //自分のいるグループの頂点数を調べる int size(int A) { return -Parent[root(A)];//親をとってきたい } //AとBをくっ付ける bool connect(int A, int B) { //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける A = root(A); B = root(B); if (A == B) { //すでにくっついてるからくっ付けない return false; } //大きい方(A)に小さいほう(B)をくっ付けたい //大小が逆だったらひっくり返しちゃう。 if (size(A) < size(B)) swap(A, B); //Aのサイズを更新する Parent[A] += Parent[B]; //Bの親をAに変更する Parent[B] = A; return true; } }; //RMQのセグ木を作るよー class SegTree { public: //二分木を配列で表したもの vector<int>seg; //木の半分の大きさ int siz; //単位元 int unit; //大きさn、unit(単位元)でsegtreeを初期化する SegTree(int n, int unit) : unit(unit) { siz = 1; while (siz < n)siz <<= 1; seg.assign(siz * 2 - 1, unit); siz--; } //k番目にtを入力 void set(int k, int t) { seg[k + siz] = t; } //木を構築する void build() { for (int i = siz - 1; 0 <= i; i--) { seg[i] = min(seg[i * 2 + 1], seg[i * 2 + 2]); } } //k番目をxに更新する void update(int k, int x) { k += siz; seg[k] = x; while (0 < k) { k = (k - 1) >> 1; seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[a,b)について、最小値を返す //半開区域のためa以上b未満の位置を指す int query(int a, int b) { int l = unit, r = unit; for (a += siz, b += siz; a < b; a >>= 1, b >>= 1) { if (!(a & 1))l = min(seg[a++], l); if (!(b & 1))r = min(seg[--b], r); } return min(l, r); } }; //aとbの最大公約数を求めるよ long long GCD(long long a, long long b) { if (b == 0) return a; else return GCD(b, a % b); } // 返り値: a と b の最大公約数 // ax + by = gcd(a, b) を満たす (x, y) が格納される long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } bool check(llint a, llint b) { return a > b; } // mod. m での a の逆元 a^{-1} を計算する long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } //aCbを1000000007で割った余りを求める llint convination(llint a, llint b) { llint ans = 1; for (llint i = 0; i < b; i++) { ans *= a - i; ans %= 1000000007; } for (llint i = 1; i <= b; i++) { ans *= modinv(i, 1000000007); ans %= 1000000007; } return ans; } //aのb乗をmodで割った余りを求める llint power(llint a, llint b) { if (b == 1)return a; if (b == 0)return 1; llint tmp = power(a, (llint)b / 2); tmp *= tmp; tmp %= mod; if (b % 2 == 1) { tmp *= a; tmp %= mod; } return tmp; } int main() { int n, q; cin >> n >> q; SegTree ST(n, Inf); rep(i, n) { int x; cin >> x; ST.set(i, x); } ST.build(); vpint lr(q); rep(i, q)cin >> lr[i].first >> lr[i].second; rep(i, q) { cout << ST.query(lr[i].first, lr[i].second) << endl; } return 0; }