Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #define MAXN 200010
- #define KONJ 42 - 42
- #define INF 1 000000000
- using namespace std;
- int N, cnt, A, B;
- int ucenici[MAXN][2];
- int sorted[MAXN];
- char s[3];
- struct input{
- int a, b, type, index;
- } niz[MAXN];
- struct _node{
- int maks, index;
- };
- struct tournament{
- int offset;
- _node tree[2 * MAXN];
- tournament( int size ){
- for ( ; offset < size; offset *= 2 );
- }
- void set( int i, int value ){
- i += offset; tree[i].maks = value; tree[i].index = i; i /= 2;
- while ( i > 0 ){
- if ( tree[2 * i].maks >= tree[2 * i + 1].maks ){
- tree[i].maks = tree[2 * i].maks; tree[i].index = tree[2 * i].index;
- } else {
- tree[i].maks = tree[2 * i + 1].maks; tree[i].index = tree[2 * i + 1].index;
- }
- i /= 2;
- }
- }
- int find( int node, int lo, int hi ){ // node sadrzi maximum u intervalu lo, hi
- if ( B >= hi ){ return INF; } // trazim desno od onog kaj trebam traziti
- if ( lo == hi && tree[node].maks >= A && lo >= B ){ return tree[node].index; }
- int left = find( 2 * node, lo, ( lo + hi ) / 2 ), right = find( 2 * node + 1, ( lo + hi ) / 2, hi );
- if ( left == INF && right == INF ){ return INF; }
- if ( left == INF && right != INF ){ return right; }
- if ( left != INF && right == INF ){ return left; }
- if ( sorted[left] <= sorted[right] ){ return left; } else { return right; }
- }
- };
- bool cmp_b( input A, input B ){
- if ( A.type != B.type ){ return A.type < B.type; }
- if ( A.b == B.b ){ return A.a < B.a; }
- return A.b < B.b;
- }
- bool cmp_index( input A, input B ){
- return A.index < B.index;
- }
- int main( void ){
- scanf( "%d", &N );
- for ( int i = 0; i < N; ++i ){
- scanf( "%s", s );
- if ( s[0] == 'D' ){
- scanf( "%d%d", &niz[i].a, &niz[i].b );
- niz[i].type = 'D'; niz[i].index = i;
- ucenici[cnt][0] = niz[i].a; ucenici[cnt++][1] = niz[i].b;
- }
- if ( s[0] == 'P' ){
- int x;
- scanf( "%d", &x );
- niz[i].a = ucenici[x - 1][0]; niz[i].b = ucenici[x - 1][1];
- niz[i].type = 'P'; niz[i].index = i;
- }
- }
- sort( niz, niz + N, cmp_b ); // imam sortane po b
- tournament T( N );
- for ( int i = 0; i < cnt; ++i ){ niz[i].b = i; sorted[i] = niz[i].a; } // za sve znam na koje mjesto idu u tournament
- sort( niz, niz + N, cmp_index );
- for ( int i = 0; i < N; ++i ){
- if ( niz[i].type == 'D' ){ T.set( niz[i].b, niz[i].a ); continue; }
- A = niz[i].a; B = niz[i].b;
- int sol = T.find( 0, 0, T.offset );
- if ( sol == INF ){ printf( "NE\n" ); } else { printf( "%d\n", sol ); }
- }
- return KONJ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement