<PREV Problem:
NEXT>
Solved by 49 users: defrager, dan, WsemirZ, DAV, JohnJones_001, Fat, topspin, Robert_Gerbicz, avg79, zloy_mipt, UdH-WiNGeR, RAVEman, kornakovBSU, Zhukov_Dmitry, Rizvanov, Darii, orban, daniel.ugra, ilyakor, Kuznetsov_S, zhuojie, Philip_PV, moon5ckq, TTLovePP, Yagi_Arthur, DPR-pavlin, fetetriste, FordPerfect, Dest, EAA2008, ignat, ripatti, abortmozga.ru, s01A15, regmar, mukel, vitar, ethanhunt, Madiyar_Tktl, shvets_175, LiuChenheng, NIGHTFIT, mikelan, bush, Nevermore, demidenko, murphy, Avitella, noh4h_ss.
UserDateAttemptTimeCMSC
Rizvanov17 sep 2009C++1201.28309 
ripatti13 jun 2010C++2001.33632 
Zhukov_Dmitry05 sep 2009C++101.33685 
vitar29 may 2011C++801.49454 
NIGHTFIT02 jun 2012C++7401.65520 
EAA200815 mar 2010C++101.77469 
JohnJones_00104 may 2009C++1202.03467 
DAV08 may 2009C++1102.10285 
Rizvanov17 sep 2009C++802.10303 
ignat03 may 2010C++1402.15777 
s01A1515 oct 2010C++102.17469 
Languages
C++
44
Kylix
2
C
2
Java
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

brackets 2

Time limit = 3 second(s)

Memory limit = 64 Mb

You are given a string consisting of the brackets "<",">"; "(",")"; "{","}"; "[","]" and a series of N pairs of integers "i j" (1 ≤ ij106)

The problem is to determine if a subsequence is a right bracket sequence (RBS)

Here is a definition of RBS: RBS + RBS = RBS; <RBS> = RBS, (RBS) = RBS, [RBS] = RBS, {RBS} = RBS.

The following sequences are RBS: (), ([]), <>()[](<>){{}}, <{{{}}()}>.

Input Sequence of brackets. The length of the sequence does not exceed 106.

N — the number of requests, N ≤ 2*106.

N lines with pairs of i and j.

Output N lines with answers: "Y" when subsequence is a RBS, "N" otherwise

Input#1
}<>(){)(<})[]
3
2 3
2 5
8 11
Output#1
Y
Y
N

Input#2
((><))>{<>}[[])
5
2 5
8 11
12 13
12 14
13 14
Output#2
N
Y
N
N
Y

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 18.210.24.208