# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
140944 | Ruxandra985 | Deda (COCI17_deda) | C++14 | 153 ms | 6840 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 <cstdio>
#include <iostream>
#define DIMN 200010
#define INF 2000000000
using namespace std;
int sol,n;
int aint[4*DIMN];
void build (int nod,int st,int dr){
int mid = (st + dr)/2;
aint[nod] = INF;
if (st == dr)
return;
build (2*nod,st,mid);
build (2*nod+1,mid+1,dr);
}
void update (int nod,int st,int dr,int x,int y){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = min(aint[nod],y);
return;
}
if (x<=mid)
update (2*nod,st,mid,x,y);
else update (2*nod+1,mid+1,dr,x,y);
aint[nod] = min (aint[2*nod] , aint[2*nod+1]);
}
void query (int nod,int st,int dr,int x,int y){
int mid = (st + dr)/2;
if (sol != -1)
return;
if (aint[nod] > y)
return;
if (x<=st && dr<=n){
if (st == dr){
sol = st;
return;
}
if (aint[2*nod]<=y)
query(2*nod,st,mid,x,y);
else query(2*nod+1,mid+1,dr,x,y);
}
else{
if (x <=mid)
query(2*nod,st,mid,x,y);
if (mid+1<=n)
query(2*nod+1,mid+1,dr,x,y);
}
}
int main()
{
//freopen ("a.in","r",stdin);
//freopen ("a.out","w",stdout);
int q,x,y;
char c;
scanf ("%d%d\n",&n,&q);
build (1,1,n);
for (;q;q--){
scanf ("%c",&c);
scanf ("%d%d\n",&x,&y);
if (c == 'M'){
update (1,1,n,y,x);
}
else {
sol = -1;
query (1,1,n,y,x);
printf ("%d\n",sol);
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |