Submission #467906

#TimeUsernameProblemLanguageResultExecution timeMemory
467906trumchepcodeDeda (COCI17_deda)C++14
80 / 140
117 ms6340 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e5+1; const long long inf=1e9+7; int n,q; long long st[4*N]; void build(int id,int l,int r) { if(l>r) return ; if(l==r) { st[id]=inf; return ; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); st[id]=min(st[id*2],st[id*2+1]); } void update(int id,int l,int r,int a,int x) { if(l>a||a>r) return ; if(l==r) { st[id]=x; return ; } int mid=(l+r)/2; update(id*2,l,mid,a,x); update(id*2+1,mid+1,r,a,x); st[id]=min(st[id*2],st[id*2+1]); } long long get(int id,int l,int r,int u,int v,int x) { if(u>v||st[id]>x||u>r||v<l) return -1; if(l==r) { return l; } int mid=(l+r)/2; int vitri=get(id*2,l,mid,u,v,x); if(vitri!=-1) return vitri; return get(id*2+1,mid+1,r,u,v,x); } void giai() { cin >> n >> q; build(1,1,n); for(int i=1;i<=q;i++) { char t; cin >> t; if(t=='M') { long long x; int a; cin >> x >> a; update(1,1,n,a,x); } else { long long x,b; cin >> x >> b; if(get(1,1,n,b,n,x)==inf) cout << "-1" << '\n'; else cout << get(1,1,n,b,n,x) << '\n'; } } } int main () { ios::sync_with_stdio(false); cin.tie(0); //freopen("corona.inp","r",stdin); //freopen("corona.out","w",stdout); giai(); }
#Verdict Execution timeMemoryGrader output
Fetching results...