Submission #250234

#TimeUsernameProblemLanguageResultExecution timeMemory
250234Vladikus004Deda (COCI17_deda)C++14
140 / 140
981 ms4984 KiB
#include <bits/stdc++.h> #define inf 2e9 #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; const int N = 200000 + 3; int n, q, t[N * 4]; void build(int v, int tl, int tr){ if (tl == tr){ t[v] = inf; }else{ int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr); t[v] = max(t[v * 2], t[v * 2 + 1]); } } int get_min(int v, int tl, int tr, int l, int r){ if (l > r) return inf; if (tl == l && tr == r){ return t[v]; } int tm = (tl + tr) / 2; return min(get_min(v * 2, tl, tm, l, min(r, tm)), get_min(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)); } void up(int v, int tl, int tr, int ind, int val){ if (tl == tr){ t[v] = val; return; } int tm = (tl + tr) / 2; if (ind <= tm) up(v * 2, tl, tm, ind, val); else up(v * 2 + 1, tm + 1, tr, ind, val); t[v] = min(t[v * 2], t[v * 2 + 1]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL cin >> n >> q; build(1, 0, n - 1); while (q--){ char c; int x, y; cin >> c >> x >> y; swap(x, y); if (c == 'M'){ up(1, 0, n - 1, x - 1, y); }else{ --x; int l = x, r = n; while (l < r){ int mid = (l + r) / 2; if (get_min(1, 0, n - 1, l, mid) <= y) r = mid; else l = mid + 1; } if (r != n){ cout << r + 1 << "\n"; }else{ cout << -1 << "\n"; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...