Submission #234431

#TimeUsernameProblemLanguageResultExecution timeMemory
234431NONAMEDeda (COCI17_deda)C++17
140 / 140
120 ms3704 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) int(x.size()) #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #define N 100500 #define oo ll(1e16) #define ft first #define sd second #define mp make_pair #define pb push_back #define ppb pop_back #define el '\n' #define elf endl #define base ll(1e9 + 7) using namespace std; typedef long long ll; typedef long double ld; int n, q; int t[8 * N]; void build(int v, int l, int r) { t[v] = 2e9; if (l >= r) return; int md = (l + r) >> 1; build(v + v, l, md); build(v + v + 1, md + 1, r); } void upd(int v, int l, int r, int ps, int vl) { if (l == r) { t[v] = vl; return; } int md = (l + r) >> 1; if (ps <= md) upd(v + v, l, md, ps, vl); else upd(v + v + 1, md + 1, r, ps, vl); t[v] = min(t[v + v], t[v + v + 1]); } int f(int v, int l, int r, int tl, int tr, int vl) { if ((l > r) || (tl > r) || (l > tr) || (t[v] > vl)) return -1; if (l == r) return l; int md = (l + r) >> 1; int c = -1; if (t[v + v] <= vl) c = f(v + v, l, md, tl, tr, vl); if (c == -1) c = f(v + v + 1, md + 1, r, tl, tr, vl); return c; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // in("input.txt"); cin >> n >> q; build(1, 0, n - 1); while (q--) { char c; cin >> c; if (c == 'D') { int x, y; cin >> x >> y; y--; int rs = f(1, 0, n - 1, y, n - 1, x); cout << (rs == -1 ? -1 : rs + 1) << el; } if (c == 'M') { int x, y; cin >> x >> y; y--; upd(1, 0, n - 1, y, x); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...