Submission #834303

#TimeUsernameProblemLanguageResultExecution timeMemory
834303serifefedartarDeda (COCI17_deda)C++17
140 / 140
96 ms6944 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); typedef long long ll; #define f first #define s second #define MOD 1000000007 #define LOGN 20 #define MAXN 200005 const int INF = 2000000000; int sg[4*MAXN]; void update(int k, int a, int b, int plc, int val) { if (b < plc || a > plc) return ; if (a == b) { sg[k] = val; return ; } update(2*k, a, (a+b)/2, plc, val); update(2*k+1, (a+b)/2+1, b, plc, val); sg[k] = min(sg[2*k], sg[2*k+1]); } int query(int k, int a, int b, int q_l, int q_r, int mx_stops) { if (b < q_l || a > q_r || sg[k] > mx_stops) return INF; if (a == b) return a; int leftQ = query(2*k, a, (a+b)/2, q_l, q_r, mx_stops); if (leftQ != INF) return leftQ; int rightQ = query(2*k+1, (a+b)/2+1, b, q_l, q_r, mx_stops); if (rightQ != INF) return rightQ; return INF; } int main() { fast int N, Q; cin >> N >> Q; for (int i = 0; i < 4*MAXN; i++) sg[i] = INF; while (Q--) { char ch; cin >> ch; if (ch == 'M') { int plc, val; cin >> val >> plc; update(1, 1, N, plc, val); } else { int stops, mn; cin >> stops >> mn; int q = query(1, 1, N, mn, N, stops); if (q == INF) cout << -1 << "\n"; else cout << q << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...