Submission #917977

#TimeUsernameProblemLanguageResultExecution timeMemory
917977MercubytheFirstDeda (COCI17_deda)C++17
140 / 140
289 ms11092 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const int N = 2e5 + 37; const ll inf = 1e17 + 37; int n, q; struct SegmentTree{ ll t[4 * N]; SegmentTree() { for(int i = 0; i < 4 * N; ++i) t[i] = inf; } void update(int idx, int val, int v = 1, int l = 1, int r = n){ assert(l <= r); if(idx < l or r < idx) return; if(l == r){ assert(l == idx); t[v] = val; return; } int m = (l + r) / 2; if(idx <= m) update(idx, val, v * 2, l, m); else update(idx, val, v * 2 + 1, m + 1, r); t[v] = min(t[v * 2], t[v * 2 + 1]); } ll wolk_dat_tree(int max_dur, int v, int l, int r){ if(l == r){ assert(t[v] <= max_dur); return l; } int m = (l + r) / 2; if(t[v * 2] <= max_dur){ return wolk_dat_tree(max_dur, v * 2, l, m); } else if(t[v * 2 + 1] <= max_dur){ return wolk_dat_tree(max_dur, v * 2 + 1, m + 1, r); } else return inf; } ll query(int min_age, int max_dur, int v = 1, int l = 1, int r = n){ if(r < min_age or t[v] > max_dur) return inf; if(min_age <= l){ return wolk_dat_tree(max_dur, v, l, r); } int m = (l + r) / 2; return min(query(min_age, max_dur, v * 2, l, m), query(min_age, max_dur, v * 2 + 1, m + 1, r)); } }; void solve(void){ cin >> n >> q; SegmentTree t; while(q--){ char qt; cin >> qt; if(qt == 'M'){ int len, child; cin >> len >> child; t.update(child, len); } else{ int min_age, max_dur; cin >> max_dur >> min_age; ll ans = t.query(min_age, max_dur); if(ans == inf) ans = -1; cout << ans << endl; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // int t; cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...