Submission #1215787


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int N;
int Q;
string S;
int sum1[100005];
int sum2[100005];
const int INF = (1<<29);

struct seg {
  int d[(1<<18)];
  int n;
  void init(int _n){
    n = 1;
    while( n < _n ) n *= 2;
    fill( d, d+n, INF );
  }
  void set(int k,int num){
    k += n-1;
    d[k] = num;
    while( k > 0 ){
      k = (k-1)/2;
      d[k] = min( d[2*k+1], d[2*k+2] );
    }
  }
  int query(int a,int b,int k,int l,int r){
    if( r <= a || b <= l ) return INF;    
    else if( a <= l && r <= b ) return d[k];
    return min( query( a, b, 2*k+1, l, (l+r)/2 ),
                query( a, b, 2*k+2, (l+r)/2, r ) );    
  }

  int query(int a, int b){
    if( a < 0 ) return 0;
    if( b >= n ) return 0;
    return query( a, b, 0, 0, n );
  }
};

seg S1,S2;
int main() {
  cin >> N;
  cin >> S;
  cin >> Q;

  int s=0;
  S1.init(N+1);
  S2.init(N+1);
  for(int i=0;i<N;i++){
    if( S[i] == '(' || S[i] == '?' ) s ++;
    else s--;
    S1.set(i,s);
  }
  reverse( S.begin(), S.end() );
  s = 0;
  for(int i=0;i<N;i++){
    if( S[i] == ')' || S[i] == '?' ) s++;
    else s--;
    S2.set(i,s);
  }

  for(int i=0;i<Q;i++){
    int l,r; cin >> l >> r;
    int rl = N-r, rr = N-l;
    l--; rr++;
    if( (r-l) % 2 == 1 ) {
      cout << "No" << endl;
      continue;
    }
                         
    //cout << S1.query(l-1,l) << " " << S1.query( l,r )<< endl;
    //cout << S2.query(rl-1,rl) << " " << S2.query( rl,rr )<< endl;
    if( S1.query(l-1,l) > S1.query(l,r) ||
        S2.query(rl-1,rl) > S2.query(rl,rr) )
      cout << "No" << endl;
    else
      cout << "Yes" << endl;    
  }
  
}

Submission Info

Submission Time
Task D - Parenthesis Sequence
User sate3saku3
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1700 Byte
Status AC
Exec Time 354 ms
Memory 2688 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 29
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
test_01.txt AC 191 ms 512 KB
test_02.txt AC 196 ms 512 KB
test_03.txt AC 198 ms 512 KB
test_04.txt AC 312 ms 2560 KB
test_05.txt AC 275 ms 2560 KB
test_06.txt AC 310 ms 2560 KB
test_07.txt AC 347 ms 2560 KB
test_08.txt AC 341 ms 2560 KB
test_09.txt AC 343 ms 2560 KB
test_10.txt AC 339 ms 2560 KB
test_11.txt AC 329 ms 2560 KB
test_12.txt AC 332 ms 2560 KB
test_13.txt AC 333 ms 2560 KB
test_14.txt AC 327 ms 2560 KB
test_15.txt AC 318 ms 2560 KB
test_16.txt AC 325 ms 2560 KB
test_17.txt AC 329 ms 2560 KB
test_18.txt AC 327 ms 2560 KB
test_19.txt AC 330 ms 2560 KB
test_20.txt AC 330 ms 2560 KB
test_21.txt AC 333 ms 2560 KB
test_22.txt AC 354 ms 2688 KB
test_23.txt AC 279 ms 2560 KB
test_24.txt AC 274 ms 2560 KB
test_25.txt AC 280 ms 2560 KB
test_26.txt AC 281 ms 2560 KB
test_27.txt AC 278 ms 2560 KB