Submission #479860

#TimeUsernameProblemLanguageResultExecution timeMemory
479860aris12345678Deda (COCI17_deda)C++14
120 / 140
1084 ms4496 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define X first #define Y second const int mxN = 200005; const int inf = 1e9+5; int st[4*mxN]; void update(int p, int l, int r, int i, int v) { if(l == r) st[p] = v; else { int md = (l+r)/2; if(i <= md) update(2*p, l, md, i, v); else update(2*p+1, md+1, r, i, v); st[p] = min(st[2*p], st[2*p+1]); } } int Min(int p, int l, int r, int i, int j) { if(i > r || l > j) return inf; if(i <= l && r <= j) return st[p]; int md = (l+r)/2; return min(Min(2*p, l, md, i, j), Min(2*p+1, md+1, r, i, j)); } inline void read(int &res){ char c; while(c = getchar(), c < '0' || c > '9') {} res = c-'0'; while(c = getchar(), c >= '0' && c <= '9') res = 10*res+c-'0'; } int main() { int n, q; read(n), read(q); fill(st, st+4*mxN, inf); while(q--) { char type; int l, r; while(type = getchar(), type != 'M' && type != 'D') {} read(l), read(r); if(type == 'M') update(1, 1, n, r, l); else { int st = r, en = n, md, ans = -1; while(st <= en) { md = (st+en)/2; if(Min(1, 1, n, r, md) <= l) ans = md, en = md-1; else st = md+1; } printf("%d\n", ans); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...