Submission #870234

#TimeUsernameProblemLanguageResultExecution timeMemory
870234falazDeda (COCI17_deda)C++17
140 / 140
85 ms7732 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define F first #define S second #define lv (v << 1) #define rv ((v << 1) | 1) #define mid ((r + l) / 2) const int N = 2e5 + 25, inf = 1e18; int n, q, seg[4 * N]; void update(int v, int l, int r, int i, int k) { if (l == r) { seg[v] = k; return; } (i <= mid) ? update(lv, l , mid, i, k) : update(rv, mid + 1, r, i, k); seg[v] = min(seg[lv], seg[rv]); } pair<int, pair<int, int>> find(int v, int l, int r, int i, int k) { // cout << v << " " << l << " " << r << " " << seg[v] << endl; if (r < i) { return {inf, {inf, inf}}; } if (l >= i) { if (seg[v] <= k) return {v, {l, r}}; else return {inf, {inf, inf}}; } pair<int, pair<int, int>> a = find(lv, l, mid, i, k); if (a.F != inf) return a; else return find(rv, mid + 1, r, i, k); } int get_ans(int v, int l, int r, int k) { if (l == r) return l; return ((seg[lv] <= k) ? get_ans(lv, l, mid, k) : get_ans(rv, mid + 1, r, k)); } void query() { cin >> n >> q; while (q--) { char s; int x, a; cin >> s >> x >> a; if (s == 'M') update(1, 1, n, a, x); else { pair<int, pair<int, int>> ans = find(1, 1, n, a, x); if (ans.F == inf) { cout << -1 << endl; } else { // cout << ans.F << " " << ans.S.F << " " << ans.S.S << endl; cout << get_ans(ans.F, ans.S.F, ans.S.S, x) << endl; } } } } void run() { memset(seg, 127, sizeof(seg)); query(); } signed main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); run(); }
#Verdict Execution timeMemoryGrader output
Fetching results...