Advertisement
Guest User

Untitled

a guest
Jul 26th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6. const int inf = 0x3f3f3f3f;
  7. const int off = ( 1 << 19 );
  8.  
  9. const int MAXN = 300005;
  10. inline int L( int x ) { return ( x ) << ( 1 ); }
  11. inline int R( int x ) { return L( x ) | ( 1 ); }
  12.  
  13. int N, Q;
  14. int a, b;
  15. char buff[ MAXN ];
  16. int s[ MAXN ], top;
  17. int ap[ MAXN ];
  18. int who[ MAXN ];
  19. int t[ off << 1 ];
  20. int lo, hi, cnt;
  21.  
  22. void build( int n ) {
  23.    if( n >= off ) return;
  24.    build( L( n ) ); build( R(n) );
  25.    t[n] = min( t[L(n)], t[R(n)] );
  26. }
  27.  
  28. int _query( int x, int y, int n ) {
  29.    if( x >= hi || y <= lo ) return inf;
  30.    if( x >= lo && y <= hi ) return t[n];
  31.    return min( _query( x, (x+y)>>1, L(n) ), _query( (x+y)>>1, y, R(n) ) );
  32. }
  33.  
  34. inline int query( int x, int y ) {
  35.    lo = x; hi = y+1;
  36.    return _query( 0, off, 1 );
  37. }
  38.  
  39. int main( void )
  40. {
  41.    scanf( "%s", buff );
  42.    int n = strlen( buff );
  43.    int mark = 0;
  44.    s[top++] = 0;
  45.    who[0] = -1;
  46.  
  47.    for( int i = 0; i < off; ++i )
  48.       t[i+off] = inf;
  49.  
  50.    for( int i = 0; i < n; ++i ) {
  51.       if( buff[i] == '(' ) {
  52.      ap[i] = cnt;
  53.      who[++mark] = i;
  54.      s[top++] = mark;
  55.      t[off+cnt++] = mark;
  56.       }
  57.       else {
  58.      --top;
  59.      t[off+cnt++] = s[top-1];
  60.       }
  61.    }
  62.  
  63.    build( 1 );
  64.    scanf( "%d", &Q );
  65.  
  66.    for( int i = 0; i < Q; ++i ) {
  67.       scanf( "%d%d", &a, &b ); --a, --b; if( a > b ) swap( a, b );
  68.       printf( "%d\n", who[query( ap[a], ap[b] )]+1 );
  69.    }
  70.  
  71.    return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement