Submission #918850

#TimeUsernameProblemLanguageResultExecution timeMemory
918850vjudge1Deda (COCI17_deda)C++17
140 / 140
102 ms8016 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=2e5+100; #else const int lim=3e3+100; #endif #include "bits/stdc++.h" using namespace std; //#define int int64_t #define pb push_back const int mod=1e9+7; using pii=pair<int,int>; struct segtree{ int tree[4*lim]; int n; segtree(int n):n(n){ for(int i=0;i<=4*n;i++){ tree[i]=INT_MAX; } } int P,VAL; void update(int l,int r,int node){ if(l==r){ tree[node]=VAL; return; } int mid=(l+r)>>1,child=node<<1; if(P<=mid)update(l,mid,child); else update(mid+1,r,child|1); tree[node]=min(tree[child],tree[child|1]); } void update(int p,int val){ P=p,VAL=val; update(1,n,1); } int query2(int l,int r,int node){ if(l==r){ return l; } int mid=(l+r)>>1,child=node<<1; if(tree[child]<=VAL) return query2(l,mid,child); return query2(mid+1,r,child|1); } int query1(int l,int r,int node){ if(VAL<tree[node]||r<P)return INT_MAX; if(P<=l)return query2(l,r,node); int mid=(l+r)>>1,child=node<<1; return min(query1(l,mid,child),query1(mid+1,r,child|1)); } int query(int p,int val){ P=p,VAL=val; int ans=query1(1,n,1); if(ans==INT_MAX)return -1; return ans; } }; inline void solve(){ int n,q; cin>>n>>q; segtree st(n); for(int i=0;i<q;i++){ char ty; int v,p; cin>>ty>>v>>p; if(ty=='M'){ st.update(p,v); }else{ cout<<st.query(p,v)<<"\n"; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #else #endif int t=1; //cin>>t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...