oj.uz

Submission #137784

# Submission time Handle Problem Language Result Execution time Memory
137784 2019-07-28T09:38:53 Z Linca_Robert Deda (COCI17_deda) C++14
140 / 140
 869 ms 8004 KB 
#include<bits/stdc++.h>
using namespace std;
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(){

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

    for( ; Q; Q-- ){

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

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

    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 21 ms 3600 KB Output is correct
4 Correct 869 ms 7988 KB Output is correct
5 Correct 681 ms 7524 KB Output is correct
6 Correct 737 ms 7752 KB Output is correct
7 Correct 790 ms 8004 KB Output is correct