Submission #464053

#TimeUsernameProblemLanguageResultExecution timeMemory
464053cinnabar233Deda (COCI17_deda)C++14
60 / 140
1096 ms4444 KiB
#include<iostream> #include<vector> #include<algorithm> #include<set> #include<stack> #include<map> #include<iomanip> #include<math.h> #include<queue> #include<cmath> #include<complex.h> #include<deque> using namespace std; #define pb push_back #define ll long long int # define pll pair<ll,ll> # define pii pair<int,int> #define sec second #define ft first #define mp make_pair #define fio ios_base::sync_with_stdio(false) int n, q ; int a[200009]; int t[800009]; void update(int v , int l , int r , int pos , int val ) { if(l == r) { t[v] = val ; return ; } int mid = (l+r)/2; if(mid < pos) update(2*v+1,mid+1,r,pos,val); else update(2*v,l,mid,pos,val); t[v] = min(t[2*v],t[2*v+1]); } int get(int v , int l , int r , int tl , int tr) { //cout << l << " " << r << tl << " " << tr << "\n"; if(tl > tr) return 1e9+1 ; if(l == tl and r == tr) return t[v]; int mid = (l+r)/2; return min(get(2*v,l,mid,tl,min(mid,tr)),get(2*v+1,mid+1,r,max(tl,mid+1),tr)); } int main() { fio; cin >> n >> q ; for(int i = 1 ; i <= 4*n ; i++) t[i] = 1e9+1 ; while(q--) { char c ; int x , y ; cin >> c >> x >> y; if(c == 'M') update(1,1,n,y,x); else { int l = y , r = n ; //cout << l << " " << r << "\n"; while(l < r) { //cout << l << " " << r << "\n"; int mid = (l+r)/2; if(get(1,1,n,y,mid) <= x) r = mid; else l = mid+1 ; } if(get(1,1,n,y,r) <= x or y > n) cout <<r << "\n"; else cout << "-1\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...