Submission #155252

#TimeUsernameProblemLanguageResultExecution timeMemory
155252GoldNextYearDeda (COCI17_deda)C++14
80 / 140
1088 ms4072 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 340 #define mid (l+r)/2 #define pb push_back #define pob pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset typedef long long ll; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll mod=1000000007; const ll inf=1e18*4; const ld pai=acos(-1); int n,q; int tree[800009]; void build(int node,int l,int r){ if(l==r){ tree[node]=1e9*2;//change it to inf return; } build(node*2,l,mid); build(node*2+1,mid+1,r); tree[node]=min(tree[node*2],tree[node*2+1]); } int query(int node,int l,int r,int s,int e){ if(s<=l && e>=r)return tree[node]; if(s<=mid && e>=mid+1)return min(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e)); else if(s<=mid)return query(node*2,l,mid,s,e); else return query(node*2+1,mid+1,r,s,e); } void upd(int node,int l,int r,int k,int val){ if(l==r){ tree[node]=val; return; } if(k<=mid)upd(node*2,l,mid,k,val); else upd(node*2+1,mid+1,r,k,val); tree[node]=min(tree[node*2],tree[node*2+1]); } int bin(int L,int x){ int l=L-1,r=n; while(r-l>1){ int m=(l+r)/2; if(query(1,0,n-1,L,m)<=x)r=m; else l=m; } if(r==n)return -1; return r+1; } int main(){ fast; cin>>n>>q; build(1,0,n-1); while(q--){ char t;cin>>t; if(t=='M'){ int id,val; cin>>val>>id; id--; upd(1,0,n-1,id,val); } else{ int l,x; cin>>x>>l; l--; cout<<bin(l,x)<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...