oj.uz

Submission #140944

# Submission time Handle Problem Language Result Execution time Memory
140944 2019-08-06T07:09:24 Z Ruxandra985 Deda (COCI17_deda) C++14
140 / 140
 153 ms 6840 KB 
#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

deda.cpp: In function 'int main()':
deda.cpp:56:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d\n",&n,&q);
     ~~~~~~^~~~~~~~~~~~~~~~
deda.cpp:59:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%c",&c);
         ~~~~~~^~~~~~~~~
deda.cpp:60:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d\n",&x,&y);
         ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 129 ms 6840 KB Output is correct
5 Correct 138 ms 5404 KB Output is correct
6 Correct 146 ms 6788 KB Output is correct
7 Correct 153 ms 6816 KB Output is correct