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