Submission #1357736
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;
int N,Q;
const int MAX_N = 1 << 17;
string S;
int segTree [MAX_N * 2],segTree2 [MAX_N * 2];
const int INF = 1e9;
void init(int segTree [])
{
fill(segTree,segTree + MAX_N * 2,INF);
}
void update(int segTree [],int idx,int val)
{
idx += MAX_N - 1;
segTree [idx] = val;
while(idx){
idx = (idx - 1) / 2;
segTree [idx] = min(segTree [idx * 2 + 1],segTree [idx * 2 + 2]);
}
}
int getMin(int segTree [],int a,int b,int idx,int l,int r)
{
if(b <= l || r <= a) return INF;
if(a <= l && r <= b) return segTree [idx];
int res = getMin(segTree,a,b,idx * 2 + 1,l,(l + r) / 2);
chmin(res,getMin(segTree,a,b,idx * 2 + 2,(l + r) / 2,r));
return res;
}
int main()
{
cin >> N >> S;
init(segTree);
init(segTree2);
vector<int> p(N + 1),q(N + 1),r(N + 1);
FOR(i,0,N){
p [i + 1] = p [i];
q [i + 1] = q [i];
r [i + 1] = r [i];
if(S [i] == '('){
p [i + 1]++;
}
else if(S [i] == ')'){
q [i + 1]++;
}
else{
r [i + 1]++;
}
update(segTree,i,p [i + 1] - q [i + 1] + r [i + 1]);
update(segTree2,i,p [i + 1] - q [i + 1] - r [i + 1]);
}
cin >> Q;
FOR(i,0,Q){
int L,R;
cin >> L >> R;
L--;
if((R - L) % 2){
puts("No");
continue;
}
int x = (R - L) / 2 - (p [R] - p [L]);
if(x > r [R] - r [L]){
puts("No");
continue;
}
int lo = L - 1,hi = R,mid;
while(hi - lo > 1){
mid = (lo + hi) / 2;
if((r [mid] - r [L]) >= x){
hi = mid;
}
else{
lo = mid;
}
}
bool ans = true;
ans &= getMin(segTree,L,hi,0,0,MAX_N) >= p [L] - q [L] + r [L];
ans &= getMin(segTree2,hi,R,0,0,MAX_N) >= p [R] - q [R] - r [R];
puts(ans ? "Yes" : "No");
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Parenthesis Sequence |
User |
gigime |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2024 Byte |
Status |
AC |
Exec Time |
311 ms |
Memory |
4096 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 |
2 ms |
2304 KB |
sample_02.txt |
AC |
2 ms |
2304 KB |
test_01.txt |
AC |
179 ms |
2560 KB |
test_02.txt |
AC |
190 ms |
2560 KB |
test_03.txt |
AC |
181 ms |
2560 KB |
test_04.txt |
AC |
257 ms |
3968 KB |
test_05.txt |
AC |
221 ms |
3968 KB |
test_06.txt |
AC |
266 ms |
4096 KB |
test_07.txt |
AC |
298 ms |
4096 KB |
test_08.txt |
AC |
301 ms |
4096 KB |
test_09.txt |
AC |
298 ms |
3968 KB |
test_10.txt |
AC |
303 ms |
3968 KB |
test_11.txt |
AC |
300 ms |
3968 KB |
test_12.txt |
AC |
304 ms |
3968 KB |
test_13.txt |
AC |
300 ms |
3968 KB |
test_14.txt |
AC |
303 ms |
3968 KB |
test_15.txt |
AC |
309 ms |
3968 KB |
test_16.txt |
AC |
305 ms |
3968 KB |
test_17.txt |
AC |
307 ms |
3968 KB |
test_18.txt |
AC |
307 ms |
3968 KB |
test_19.txt |
AC |
307 ms |
3968 KB |
test_20.txt |
AC |
307 ms |
3968 KB |
test_21.txt |
AC |
311 ms |
4096 KB |
test_22.txt |
AC |
310 ms |
4096 KB |
test_23.txt |
AC |
257 ms |
3968 KB |
test_24.txt |
AC |
247 ms |
3968 KB |
test_25.txt |
AC |
260 ms |
3968 KB |
test_26.txt |
AC |
249 ms |
3968 KB |
test_27.txt |
AC |
253 ms |
3968 KB |