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 |
|
|
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 |