Submission #869481

#TimeUsernameProblemLanguageResultExecution timeMemory
869481IrateDeda (COCI17_deda)C++14
140 / 140
151 ms7972 KiB
#include<bits/stdc++.h> using namespace std; struct SegmentTree{ vector<int>sTree; SegmentTree(int n){ sTree.resize(4 * n); } void Build(int node, int l, int r){ if(l == r){ sTree[node] = 2e9; } else{ int mid = (l + r) >> 1; Build(node * 2, l, mid); Build(node * 2 + 1, mid + 1, r); sTree[node] = min(sTree[node * 2], sTree[node * 2 + 1]); } } void Update(int node, int l, int r, int pos, int val){ if(l == r){ sTree[node] = val; } else{ int mid = (l + r) >> 1; if(pos <= mid){ Update(node * 2, l, mid, pos, val); } else{ Update(node * 2 + 1, mid + 1, r, pos, val); } sTree[node] = min(sTree[node * 2], sTree[node * 2 + 1]); } } int Query(int node, int l, int r, int ql, int qr, int x){ if(ql <= l && r <= qr){ if(l == r){ if(sTree[node] <= x)return l; return 2e9; } int mid = (l + r) >> 1; if(sTree[node * 2] <= x)return Query(node * 2, l, mid, ql, qr, x); return Query(node * 2 + 1, mid + 1, r, ql, qr, x); } if(ql > r || l > qr)return 2e9; int mid = (l + r) >> 1; int lc = Query(node * 2, l, mid, ql, qr, x); int rc = Query(node * 2 + 1, mid + 1, r, ql, qr, x); if(lc == 2e9)return rc; return lc; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; SegmentTree tree(n); tree.Build(1, 1, n); while(q--){ char type; int y, b; cin >> type >> y >> b; if(type == 'M'){ tree.Update(1, 1, n, b, y); } else{ int pos = tree.Query(1, 1, n, b, n, y); if(pos == 2e9)cout << -1 << '\n'; else cout << pos << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...