Submission #792398

#TimeUsernameProblemLanguageResultExecution timeMemory
792398Nhoksocqt1Deda (COCI17_deda)C++17
140 / 140
72 ms7548 KiB
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define sz(x) int((x).size()) #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } const int MAXN = 200005; int posInTree[MAXN], seg[4 * MAXN], nArr, numQuery; void build(int id, int l, int r) { seg[id] = 1e9+7; if(l == r) { posInTree[l] = id; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); } void update(int pos, int val) { int id(posInTree[pos]); seg[id] = val; while(id > 1) { id >>= 1; seg[id] = min(seg[id << 1], seg[id << 1 | 1]); } } int walkOnSeg(int id, int l, int r, int u, int v, int k) { if(v < l || u > r || seg[id] > k) return -1; if(u <= l && r <= v) { while(l < r) { int mid = (l + r) >> 1; if(seg[id << 1] <= k) { id = id << 1; r = mid; } else { id = id << 1 | 1; l = mid + 1; } } return l; } int mid = (l + r) >> 1; int qr = walkOnSeg(id << 1, l, mid, u, v, k); if(qr != -1) return qr; return walkOnSeg(id << 1 | 1, mid + 1, r, u, v, k); } void process() { cin >> nArr >> numQuery; build(1, 1, nArr); for (int t = 0; t < numQuery; ++t) { char c; int u, v; cin >> c >> u >> v; if(c == 'M') { update(v, u); } else { int ans = walkOnSeg(1, 1, nArr, v, nArr, u); cout << ans << '\n'; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); process(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...