Submission #85659

#TimeUsernameProblemLanguageResultExecution timeMemory
85659heonDeda (COCI17_deda)C++11
140 / 140
142 ms8232 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 200005; int seg[MAXN * 4]; int query(int v, int l, int r, int L, int R, int val){ if(l > R || r < L) return INT_MAX; if(l == r) return l; int m = (l + r) / 2; int ret = INT_MAX; if(seg[v * 2] <= val){ ret = min(ret, query(v * 2, l, m, L, R, val)); if(ret != INT_MAX) return ret; } if(seg[v * 2 + 1] <= val) ret = min(ret, query(v * 2 + 1, m + 1, r, L, R, val)); return ret; } void update(int v, int l, int r, int pos, int val){ if(l == r) seg[v] = val; else{ int m = (l + r) / 2; (pos <= m ? update(v * 2, l, m, pos, val) : update(v * 2 + 1, m + 1, r, pos, val)); seg[v] = min(seg[v * 2], seg[v * 2 + 1]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,q; cin >> n >> q; for(int i = 0; i <= n * 4; i++) seg[i] = INT_MAX; while(q--){ char a; int b,c; cin >> a >> b >> c; if(a == 'M'){ update(1, 1, n, c, b); } else{ int res = query(1, 1, n, c, n, b); cout << (res == INT_MAX ? -1 : res) << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...