Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. #define MAXN 200010
  5. #define KONJ 42 - 42
  6. #define INF 1   000000000
  7.  
  8. using namespace std;
  9.  
  10. int N, cnt, A, B;
  11. int ucenici[MAXN][2];
  12. int sorted[MAXN];
  13. char s[3];
  14.  
  15. struct input{
  16.        int a, b, type, index;
  17. } niz[MAXN];
  18.  
  19. struct _node{
  20.        int maks, index;
  21. };
  22.  
  23. struct tournament{
  24.  
  25.        int offset;
  26.        _node tree[2 * MAXN];
  27.        
  28.        tournament( int size ){
  29.                    for ( ; offset < size; offset *= 2 );
  30.        }
  31.        
  32.        void set( int i, int value ){
  33.             i += offset; tree[i].maks = value; tree[i].index = i; i /= 2;
  34.             while ( i > 0 ){
  35.                   if ( tree[2 * i].maks >= tree[2 * i + 1].maks ){
  36.                      tree[i].maks = tree[2 * i].maks; tree[i].index = tree[2 * i].index;
  37.                   } else {
  38.                      tree[i].maks = tree[2 * i + 1].maks; tree[i].index = tree[2 * i + 1].index;
  39.                   }
  40.                   i /= 2;
  41.             }
  42.        }
  43.  
  44.        int find( int node, int lo, int hi ){ // node sadrzi maximum u intervalu lo, hi
  45.            if ( B >= hi ){ return INF; } // trazim desno od onog kaj trebam traziti
  46.            if ( lo == hi && tree[node].maks >= A && lo >= B ){ return tree[node].index; }
  47.            int left = find( 2 * node, lo, ( lo + hi ) / 2 ), right = find( 2 * node + 1, ( lo + hi ) / 2, hi );
  48.            if ( left == INF && right == INF ){ return INF; }
  49.            if ( left == INF && right != INF ){ return right; }
  50.            if ( left != INF && right == INF ){ return left; }
  51.            if ( sorted[left] <= sorted[right] ){ return left; } else { return right; }
  52.        }
  53.  
  54. };
  55.  
  56. bool cmp_b( input A, input B ){
  57.      if ( A.type != B.type ){ return A.type < B.type; }
  58.      if ( A.b == B.b ){ return A.a < B.a; }
  59.      return A.b < B.b;
  60. }
  61.  
  62. bool cmp_index( input A, input B ){
  63.      return A.index < B.index;
  64. }
  65.  
  66. int main( void ){
  67.  
  68.     scanf( "%d", &N );
  69.     for ( int i = 0; i < N; ++i ){
  70.         scanf( "%s", s );
  71.         if ( s[0] == 'D' ){
  72.            scanf( "%d%d", &niz[i].a, &niz[i].b );
  73.            niz[i].type = 'D'; niz[i].index = i;
  74.            ucenici[cnt][0] = niz[i].a; ucenici[cnt++][1] = niz[i].b;
  75.         }
  76.         if ( s[0] == 'P' ){
  77.            int x;
  78.            scanf( "%d", &x );
  79.            niz[i].a = ucenici[x - 1][0]; niz[i].b = ucenici[x - 1][1];
  80.            niz[i].type = 'P'; niz[i].index = i;
  81.         }
  82.     }
  83.    
  84.     sort( niz, niz + N, cmp_b ); // imam sortane po b
  85.    
  86.     tournament T( N );
  87.     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
  88.    
  89.     sort( niz, niz + N, cmp_index );
  90.     for ( int i = 0; i < N; ++i ){
  91.         if ( niz[i].type == 'D' ){ T.set( niz[i].b, niz[i].a ); continue; }
  92.         A = niz[i].a; B = niz[i].b;
  93.         int sol = T.find( 0, 0, T.offset );
  94.         if ( sol == INF ){ printf( "NE\n" ); } else { printf( "%d\n", sol ); }
  95.     }
  96.  
  97.     return KONJ;
  98.  
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement