oj.uz

Submission #137780

# Submission time Handle Problem Language Result Execution time Memory
137780 2019-07-28T09:37:33 Z Linca_Robert Deda (COCI17_deda) C++14
0 / 140
 5 ms 3452 KB 
#include<bits/stdc++.h>
using namespace std;

ifstream fin("deda.in");
ofstream fout("deda.out");

const int DIM = 2e5 + 5;

int aib[DIM * 4], N, Q, ans, pos;

void update( int nod, int st, int dr, int p, int x ){
    if( st == dr )
        aib[nod] = x;
    else{
        int mid = ( st + dr ) >> 1;
        if( p <= mid )
            update( (nod<<1)^0, st, mid + 0, p, x );
        else
            update( (nod<<1)|1, mid + 1, dr, p, x );
        aib[nod] = min( aib[(nod<<1)^0], aib[(nod<<1)|1] );
    }
}

void query( int nod, int st, int dr, int p, int x ){
    int Nst = (nod<<1)^0;
    int Ndr = (nod<<1)|1;

    if( ans != 0x3f3f3f3f )
        return;

    if( st == dr && aib[nod] <= x && ans == 0x3f3f3f3f ){
        ans = aib[nod], pos = st;
        return;
    }

    if( p <= st ){
        if( aib[nod] > x )
            return;
        int m = ( st + dr ) >>  1;
        if( aib[Nst] <= x )
            query( Nst, st, m + 0, p, x );
        else
            query( Ndr, m + 1, dr, p, x );
    }else{
        int mid = ( st + dr ) >> 1;
        if( p <= mid )
            query( Nst, st, mid + 0, p, x );
        query( Ndr, mid + 1, dr, p, x );
    }
}

int main(){

    fin >> N >> Q;
    memset( aib, 0x3f3f3f3f, sizeof(aib) );

    for( ; Q; Q-- ){

        char op; int x, p; fin >> op >> x >> p;

        if( op == 'M' )
            update( 1, 1, N, p, x );
        else{
            ans = 0x3f3f3f3f;
            query( 1, 1, N, p, x );
            fout << ( ans == 0x3f3f3f3f ? -1 : pos ) << "\n";
        }

    }
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3448 KB Output isn't correct
2 Incorrect 5 ms 3448 KB Output isn't correct
3 Incorrect 5 ms 3448 KB Output isn't correct
4 Incorrect 4 ms 3448 KB Output isn't correct
5 Incorrect 4 ms 3452 KB Output isn't correct
6 Incorrect 4 ms 3448 KB Output isn't correct
7 Incorrect 4 ms 3448 KB Output isn't correct