Submission #845882

#TimeUsernameProblemLanguageResultExecution timeMemory
845882Mr_PhDeda (COCI17_deda)C++14
140 / 140
87 ms9032 KiB
///Never gonna give you up. #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; typedef long long int lli; typedef unsigned long long ull; using namespace std; using namespace __gnu_pbds; template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>; const ll mod=(ll)1e9+7; const ll mod1=998244353; ///the defines :) #define endl '\n' #define vi vector<int> #define vll vector<ll> #define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i]; #define all(arr) arr.begin(),arr.end() #define allr(arr) arr.rbegin(),arr.rend() #define sz size() #define int long long struct segtree { int siz; vector<int>vals; int neutram_element=0; void init(int n) { siz=1; while(siz<n)siz*=2; vals.resize(siz*2); } int merg(int a,int b) { return min(a,b); } int single(int a) { return a; } void Set(int i,int val,int x,int lx,int rx) { // cout<<lx<<" "<<rx<<" "<<x<<endl; if(lx==rx) { vals[x]=single(val); return; } int mid=(lx+rx+1)/2; if(i<mid) Set(i,val,2*x+1,lx,mid-1); else Set(i,val,2*x+2,mid,rx); vals[x]=merg(vals[2*x+1],vals[2*x+2]); } void Set(int i,int v) { Set(i,v,0,0,siz-1); } int calc(int l,int r,int v,int x,int lx,int rx) { if(lx>r||rx<l||vals[x]>v)return 1e9+2; if(lx==rx)return lx; int mid=(lx+rx+1)/2; // cout<<lx<<" "<<rx<<" "<<x<<" "<<mid<<endl; int e=calc(l,r,v,2*x+1,lx,mid-1); if(e==1e9+2) e=calc(l,r,v,2*x+2,mid,rx); return e; } int calc(int l,int r,int v) { return calc(l,r,v,0,0,siz-1); } }; void preprocess() {} void solve() { int n,q; cin>>n>>q; segtree st; st.init(n); for(int i=0;i<n;i++) st.Set(i,1e9+2); while(q--) { char x; cin>>x; if(x=='M') { int a,b; cin>>a>>b; b--; st.Set(b,a); } else { int a,b; cin>>a>>b; b--; int haha=st.calc(b,n-1,a); if(haha==1e9+2)cout<<-1<<endl; else cout<<haha+1<<endl; } } } signed main() { // freopen("div7.in","r",stdin); //freopen("div7.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); preprocess(); //bla(); int t=1; // cin>>t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...