Submission #466692

#TimeUsernameProblemLanguageResultExecution timeMemory
466692ak2006Deda (COCI17_deda)C++14
140 / 140
185 ms23492 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } struct Node { int l,r; ll m = inf; Node*lc = NULL; Node*rc = NULL; Node(int L,int R) { l = L,r = R; if (l != r){ int mid = (l + r)/2; lc = new Node(l,mid); rc = new Node(mid + 1,r); } } }; void update(Node*root,int i,int v) { if (!(root->l <= i and i <= root->r))return; if (root->l == root->r){ root->m = v; return; } update(root->lc,i,v); update(root->rc,i,v); root->m = min(root->lc->m,root->rc->m); } ll walk(Node*root,int b,ll y) { if (root->r < b)return inf; if (root->m > y)return inf; if (root->l == root->r) return (root->m <= y ? root->l : inf); ll v1 = walk(root->lc,b,y); if (v1 == inf)return walk(root->rc,b,y); return v1; } int main() { setIO(); int n,q; cin>>n>>q; Node*root = new Node(1,n); while (q--){ char t; int x,a; cin>>t>>x>>a; if (t == 'M')update(root,a,x); else { ll ans = walk(root,a,x); if (ans == inf)cout<<-1<<'\n'; else cout<<ans<<'\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...