제출 #82461

#제출 시각아이디문제언어결과실행 시간메모리
82461GenezioDeda (COCI17_deda)C++14
140 / 140
195 ms3804 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define mp make_pair #define F first #define S second #define pb push_back #define ll long long #define fe 2*x+1 #define fd 2*x+2 #define m ((l+r)>>1) const int N = 200010; const int INF = 0x3f3f3f3f; const ll mod = 1e9+7; int v[N]; int tree[4*N]; void build(int x,int l,int r) { if(l==r) { tree[x]=INF; return; } build(fe,l,m); build(fd,m+1,r); tree[x]=min(tree[fe],tree[fd]); } void upd(int x,int l,int r,int p,int v) { if(l==r) { tree[x]=v; return; } if(p<=m) { upd(fe,l,m,p,v); } else { upd(fd,m+1,r,p,v); } tree[x]=min(tree[fe],tree[fd]); } int query(int x,int l,int r,int ql,int qr,int v) { if(r<ql||l>qr) { return INF; } if(l==r) { if(tree[x]<=v) return l; else return INF; } if(ql<=l&&r<=qr) { if(tree[fe]<=v) return query(fe,l,m,ql,qr,v); else if(tree[fd]<=v) return query(fd,m+1,r,ql,qr,v); else return INF; } return min(query(fe,l,m,ql,qr,v),query(fd,m+1,r,ql,qr,v)); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,q,a,b; char c; cin>>n>>q; build(0,0,n-1); for(int i=0;i<q;i++) { cin>>c>>a>>b; if(c=='M') { upd(0,0,n-1,b-1,a); } else { int aux=query(0,0,n-1,b-1,n-1,a); if(aux==INF) cout<<"-1\n"; else cout<<aux+1<<"\n"; } } /*for(int i=0;i<4*n;i++) { cout<<i<<" "<<tree[i]<<"\n"; }*/ return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...