#include<iostream>
#include<fstream>
#define fin cin
#define fout cout
using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
int v[600001],a,b,n,q,ok;
char c;
void build(int i,int st,int dr)
{
v[i]=1000000001;
if(st!=dr)
{
int mid=(st+dr)/2;
build(i*2,st,mid);build(i*2+1,mid+1,dr);
}
}
void update(int i,int st,int dr,int val,int poz)
{
if(st==dr) v[i]=val;
else
{
int mid=(st+dr)/2;
if(st<=poz&&poz<=mid) update(i*2,st,mid,val,poz);
else update(i*2+1,mid+1,dr,val,poz);
v[i]=min(v[i*2],v[i*2+1]);
}
}
void quarry(int i,int st,int dr,int a,int b,int y)
{
if(ok!=-1) return;
if(st==dr){if(v[i]<=y&&a<=st&&st<=b) ok=st; return;}
int mid=(st+dr)/2;
if(!(a<=st&&dr<=b))
{
if(a<=mid) quarry(i*2,st,mid,a,b,y);
if(ok!=-1) return;
if(mid+1<=b) quarry(i*2+1,mid+1,dr,a,b,y);
return;
}
if(v[2*i]<=y)
{
quarry(i*2,st,mid,a,b,y);
return;
}
if(v[2*i+1]<=y) quarry(i*2+1,mid+1,dr,a,b,y);
}
int main(){
fin>>n>>q;
build(1,1,n);
for(;q--;)
{
fin>>c;fin>>a>>b;///a stop b copil
if(c=='M') update(1,1,n,a,b);
if(c=='D')
{
ok=-1;
quarry(1,1,n,b,n,a);
fout<<ok<<"\n";
}
//for(int i=1;i<=2*n-1;i++) fout<<v[i]<<" ";
//fout<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
18 ms |
376 KB |
Output is correct |
| 4 |
Correct |
892 ms |
7120 KB |
Output is correct |
| 5 |
Correct |
694 ms |
2172 KB |
Output is correct |
| 6 |
Correct |
760 ms |
6908 KB |
Output is correct |
| 7 |
Correct |
798 ms |
6980 KB |
Output is correct |
