Submission #873908

#TimeUsernameProblemLanguageResultExecution timeMemory
873908noiaintDeda (COCI17_deda)C++17
140 / 140
118 ms23632 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1 << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = 1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int inf = 1e9; // INT_MAX; const long long llinf = 1e18; // LLONG_MAX; template<class X, class Y> bool minimize(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maximize(X &a, Y b) { return a < b ? (a = b, true) : false; } template<class X, class Y> bool add(X &a, Y b) { a += b; while (a >= mod) a -= mod; while (a < 0) a += mod; return true; } struct node { int L, R, M, val; node *l, *r; node(int _L, int _R) { L = _L; R = _R; M = (L + R) >> 1; val = 1e9; if (L < R) { l = new node(L, M); r = new node(M + 1, R); } } void modify(int i, int c) { if (i < L || i > R) return; if (L == R) { val = c; return; } if (i <= M) l->modify(i, c); else r->modify(i, c); val = min(l->val, r->val); } int find(int i, int c) { if (i > R) return -1; if (L == R) return val > c ? -1 : L; int x = -1; if (l->val <= c) x = l->find(i, c); if (x != -1) return x; else return r->find(i, c); } } *root; int n, q; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q; root = new node(1, n); while (q--) { char c; int x, y; cin >> c >> x >> y; if (c == 'M') { root->modify(y, x); } else { cout << root->find(y, x) << '\n'; } } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...