Submission #633202

#TimeUsernameProblemLanguageResultExecution timeMemory
633202IwanttobreakfreeDeda (COCI17_deda)C++17
80 / 140
1086 ms11100 KiB
#include <iostream> #include <vector> using namespace std; #define int long long void pupd(int n,int l,int r,vector<int>& t,int a,int x){ if(l>a||r<a)return; if(l==r&&l==a)t[n]=x; else{ int mid=(r+l)/2; pupd(n<<1,l,mid,t,a,x); pupd((n<<1)+1,mid+1,r,t,a,x); t[n]=min(t[n<<1],t[(n<<1)+1]); } } int find_child(int n,int l,int r,vector<long long>& t,int a,int x){ if(r<a||t[n]>x)return 1e18; if(l==r&&t[n]<=x)return l; int mid=(r+l)/2; int ans1=find_child(n<<1,l,mid,t,a,x); int ans2=find_child((n<<1)+1,mid+1,r,t,a,x); return min(ans1,ans2); } signed main(){ int n,q,x,y; cin>>n>>q; char c; vector<int> t(4*n,1e18); while(q--){ cin>>c>>x>>y; y--; if(c=='M')pupd(1,0,n-1,t,y,x); else { int ans=find_child(1,0,n-1,t,y,x); if(ans==1e18)cout<<-1<<'\n'; else cout<<ans+1<<'\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...