Submission #165790

#TimeUsernameProblemLanguageResultExecution timeMemory
165790muhi1112Deda (COCI17_deda)C++17
120 / 140
1075 ms9248 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define f1 first #define s2 second #define pb push_back #define mp make_pair #define ll long long #define fri(a) freopen(a,"r",stdin); #define fro(a) freopen(a,"w",stdout); const int N=2e5+5; ll n,m,x,y,dizi[N]; pair<int,int>seg[4*N],k; char c; void update(int v,int tl,int tr,int pos,int val){ if(tl==tr){ seg[v]={val,tl}; } else{ int tm=(tl+tr)/2; if(pos<=tm){ update(v*2,tl,tm,pos,val); } else{ update(v*2+1,tm+1,tr,pos,val); } seg[v]=min(seg[v*2],seg[v*2+1]); } } pair<int,int> query(int v,int tl,int tr,int l,int r,int val){ if(l<=tl && r>=tr){ return (seg[v].f1)<=val?seg[v]:mp(INT_MAX,-1); } if(tr<l || tl>r){ return {INT_MAX,-1}; } int tm=(tl+tr)/2; pair<int,int> left=query(v*2,tl,tm,l,r,val); pair<int,int> right=query(v*2+1,tm+1,tr,l,r,val); if(left.f1<=val && right.f1<=val){ return left; } return min(left,right); } int main(){ //fri("in.txt"); //fro("out.txt"); ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; for(int i=0;i<4*N;i++){ seg[i]={INT_MAX,-1}; if(i<N)dizi[i]=INT_MAX; } for(int i=0;i<m;i++){ cin>>c>>x>>y; if(c=='M'){ update(1,1,n,y,x); dizi[y]=x; // for(int j=0;j<2*n;j++){ // cout<<seg[j].f1<<"----"<<seg[j].s2<<" "; // } // cout<<endl; } else{ k=query(1,1,n,y,n,x); if(k.s2==-1)cout<<k.s2<<endl; else{ for(int i=k.s2;i>=y;i--){ if(dizi[i]<=x){ k.f1=dizi[i]; k.s2=i; } } cout<<k.s2<<endl; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...