Submission #52829

#TimeUsernameProblemLanguageResultExecution timeMemory
52829polyfishDeda (COCI17_deda)C++14
140 / 140
129 ms18388 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n'; #define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n'; #define FILE_NAME "data" const int INF = 1e9; struct segmentTree { vector<int> st; int n; segmentTree(int _n) { n = _n; st.resize(4*n, INF); } void upd(int pos, int val, int l, int r, int id) { if (pos<l || pos>r) return; if (l==pos && pos==r) { st[id] = val; return; } int mid = (l + r) / 2; upd(pos, val, l, mid, id*2); upd(pos, val, mid+1, r, id*2+1); st[id] = min(st[id*2], st[id*2+1]); } int Find(int bound, int y, int l, int r, int id) { if (r<bound || st[id]>y) return -1; if (l==r) return l; int mid = (l + r) / 2; int tmp = Find(bound, y, l, mid, id*2); if (tmp>-1) return tmp; return Find(bound, y, mid+1, r, id*2+1); } void upd(int pos, int val) { upd(pos, val, 1, n, 1); } int Find(int b, int y) { return Find(b, y, 1, n, 1); } }; void solve() { int n, nQuery; cin >> n >> nQuery; segmentTree tr(n); while (nQuery--) { char opt; cin >> opt; if (opt=='M') { int x, a; cin >> x >> a; tr.upd(a, x); } else { int y, b; cin >> y >> b; cout << tr.Find(b, y) << '\n'; } } } int main() { //freopen(FILE_NAME".inp", "r", stdin); //freopen(FILE_NAME".out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...