Submission #137784

#	Time	Username	Problem	Language	Result	Execution time	Memory
137784		Linca_Robert	Deda (COCI17_deda)	C++14	140 / 140	869 ms	8004 KiB

deda

#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 / 140