# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
165789 | muhi1112 | Deda (COCI17_deda) | C++17 | 1004 ms | 11456 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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");
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;
break;
}
}
cout<<k.s2<<endl;
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |