fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5.  
  6.  
  7. class BRCKTS {
  8. static int a[];
  9. 	public static void main(String[] args) throws IOException {
  10. 		// TODO Auto-generated method stub
  11. Reader r=new Reader();
  12. StringBuilder sb=new StringBuilder();
  13. PrintWriter pr=new PrintWriter(System.out);
  14. int i=1;
  15. while(true){
  16.  
  17. 	String sr=r.readLine();
  18. 	if(sr==null || sr.equalsIgnoreCase(""))break;
  19. 	sb.append("Test "+(i++)+":\n");
  20. int n=Integer.parseInt(sr);
  21. boolean odd=false;
  22. if((n&1)==1)odd=true;
  23.  a=new int[n+1];
  24. String s=r.readLine();
  25. for(int j=1;j<=n;j++){
  26. 	a[j]=s.charAt(j-1)=='('?1:-1;
  27. }
  28. Segment_Tree st=new Segment_Tree(1, n);
  29. int m=r.nextInt();
  30.  
  31. for(int j=0;j<m;j++){
  32. 	int q=r.nextInt();
  33.  
  34. 	if(q==0){
  35. 		if(odd)sb.append("NO\n");
  36. 		else if(st.sum==0 && st.min_sum==0)sb.append("YES\n");
  37. 		else sb.append("NO\n");
  38. 	}
  39. 	else st.update(q);
  40. 	//System.out.println("H");
  41. }
  42. }
  43. pr.write(sb.toString());
  44. pr.flush();
  45. }
  46. 	static class Segment_Tree{
  47. 		int start,end,sum,min_sum;
  48. 		Segment_Tree left_child,right_child;
  49.  
  50. 		public Segment_Tree(){};
  51. 		public Segment_Tree(int a,int b){
  52. 			start=a;end=b;
  53. 			if(start!=end){
  54. 				int mid=(start+end)>>1;
  55. 				left_child=new Segment_Tree(a,mid);
  56. 				right_child=new Segment_Tree(mid+1,b);
  57. 				join(this,left_child,right_child);
  58. 			}
  59. 			else {
  60. 				sum=min_sum=BRCKTS.a[start]==1?1:-1;
  61. 			}
  62. 		}
  63. 		public void join(Segment_Tree parent,Segment_Tree leftchild,Segment_Tree rightchild){
  64. 			parent.sum=leftchild.sum+rightchild.sum;
  65. 			parent.min_sum=Math.min(leftchild.min_sum,rightchild.min_sum+leftchild.sum);
  66. 		}
  67. 		public void update(int index){
  68. 			if(start==index && end==index){
  69. 				sum=min_sum=min_sum==1?-1:1;
  70. 				return ;
  71. 			}
  72. 			int mid=(start+end)>>1;
  73. 			if(index<=mid)left_child.update(index);
  74. 			else if(index>mid)right_child.update(index);
  75. 			join(this, left_child, right_child);
  76. 		}
  77. 	}
  78. static class Reader {
  79. 	final private int BUFFER_SIZE = 1 << 16;
  80. 	private DataInputStream din;
  81. 	private byte[] buffer;
  82. 	private int bufferPointer, bytesRead;
  83.  
  84. 	public Reader() {
  85. 		din = new DataInputStream(System.in);
  86. 		buffer = new byte[BUFFER_SIZE];
  87. 		bufferPointer = bytesRead = 0;
  88. 	}
  89.  
  90. 	public Reader(String file_name) throws IOException {
  91. 		din = new DataInputStream(new FileInputStream(file_name));
  92. 		buffer = new byte[BUFFER_SIZE];
  93. 		bufferPointer = bytesRead = 0;
  94. 	}
  95.  
  96. 	public String readLine() throws IOException {
  97. 		byte[] buf = new byte[64];
  98. 		int cnt = 0, c;
  99. 		while ((c = read()) != -1) {
  100. 			if (c == '\n')
  101. 				break;
  102. 			buf[cnt++] = (byte) c;
  103. 		}
  104. 		return new String(buf, 0, cnt);
  105. 	}
  106.  
  107. 	public int nextInt() throws IOException {
  108. 		int ret = 0;
  109. 		byte c = read();
  110. 		while (c <= ' ')
  111. 			c = read();
  112. 		boolean neg = (c == '-');
  113. 		if (neg)
  114. 			c = read();
  115. 		do {
  116. 			ret = ret * 10 + c - '0';
  117. 		} while ((c = read()) >= '0' && c <= '9');
  118. 		if (neg)
  119. 			return -ret;
  120. 		return ret;
  121. 	}
  122.  
  123. 	public long nextLong() throws IOException {
  124. 		long ret = 0;
  125. 		byte c = read();
  126. 		while (c <= ' ')
  127. 			c = read();
  128. 		boolean neg = (c == '-');
  129. 		if (neg)
  130. 			c = read();
  131. 		do {
  132. 			ret = ret * 10 + c - '0';
  133. 		} while ((c = read()) >= '0' && c <= '9');
  134. 		if (neg)
  135. 			return -ret;
  136. 		return ret;
  137. 	}
  138.  
  139. 	public double nextDouble() throws IOException {
  140. 		double ret = 0, div = 1;
  141. 		byte c = read();
  142. 		while (c <= ' ')
  143. 			c = read();
  144. 		boolean neg = (c == '-');
  145. 		if (neg)
  146. 			c = read();
  147. 		do {
  148. 			ret = ret * 10 + c - '0';
  149. 		} while ((c = read()) >= '0' && c <= '9');
  150. 		if (c == '.')
  151. 			while ((c = read()) >= '0' && c <= '9')
  152. 				ret += (c - '0') / (div *= 10);
  153. 		if (neg)
  154. 			return -ret;
  155. 		return ret;
  156. 	}
  157.  
  158. 	private void fillBuffer() throws IOException {
  159. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  160. 		if (bytesRead == -1)
  161. 			buffer[0] = -1;
  162. 	}
  163.  
  164. 	private byte read() throws IOException {
  165. 		if (bufferPointer == bytesRead)
  166. 			fillBuffer();
  167. 		return buffer[bufferPointer++];
  168. 	}
  169.  
  170. 	public void close() throws IOException {
  171. 		if (din == null)
  172. 			return;
  173. 		din.close();
  174. 	}
  175. }
  176.  
  177. }
  178. /*
  179. 12
  180. (()(()(())))
  181. 16
  182. 0
  183. 1
  184. 3
  185. 0
  186. 4
  187. 5
  188. 6
  189. 0
  190. 10
  191. 0
  192. 2
  193. 0
  194. 1
  195. 3
  196. 4
  197. 0
  198. */
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin
copy 
4
()((
4
4
0
2
0
stdout
copy 
Test 1:
YES
NO
https://ideone.com/sKGXyr
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!