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. //Segment_Tree.print_postOrder(st);
  30. int m=r.nextInt();
  31.  
  32. for(int j=0;j<m;j++){
  33. 	int q=r.nextInt();
  34.  
  35. 	if(q==0){
  36.  
  37. 	//	else if(st.sum==0 && st.min_sum==0)sb.append("YES\n");
  38. 		 if(st.number_of_closed_unbalanced==0 && st.number_of_open_unbalanced==0 )sb.append("YES\n");
  39. 		else sb.append("NO\n");
  40. 	}
  41. 	else st.update(q);
  42. 	//System.out.println(st.sum+" "+st.min_sum);
  43. 	//System.out.println("H");
  44. }
  45. }
  46. pr.write(sb.toString());
  47. pr.flush();
  48. }
  49. 	static class Segment_Tree{
  50. 		int start,end,number_of_open_unbalanced,number_of_closed_unbalanced;
  51. 		Segment_Tree left_child,right_child;
  52. 		//int sum,min_sum;
  53. 		public Segment_Tree(){};
  54. 		public Segment_Tree(int a,int b){
  55. 			start=a;end=b;
  56. 			if(start!=end){
  57. 				int mid=(start+end)>>1;
  58. 				left_child=new Segment_Tree(a,mid);
  59. 				right_child=new Segment_Tree(mid+1,b);
  60. 				join(this,left_child,right_child);
  61. 			}
  62. 			else {
  63. 				//sum=min_sum=BRCKTS.a[start]==1?1:-1;
  64. 				if(BRCKTS.a[start]==1)
  65. 					number_of_open_unbalanced=1;
  66. 				else number_of_closed_unbalanced=1;
  67. 			}
  68. 		}
  69. 		public void join(Segment_Tree parent,Segment_Tree leftchild,Segment_Tree rightchild){
  70. 			//parent.sum=leftchild.sum+rightchild.sum;
  71. 			//parent.min_sum=Math.min(leftchild.min_sum,rightchild.min_sum+leftchild.sum);
  72. 			parent.number_of_closed_unbalanced=leftchild.number_of_closed_unbalanced;
  73. 			parent.number_of_open_unbalanced=rightchild.number_of_open_unbalanced;
  74. 			int unbala=rightchild.number_of_closed_unbalanced-leftchild.number_of_open_unbalanced;
  75. 			if(unbala>0){
  76. 			parent.number_of_closed_unbalanced+=unbala;
  77. 			}
  78. 			else parent.number_of_open_unbalanced+=Math.abs(unbala);
  79. 		}
  80. 		public void update(int index){
  81. 			if(start==index && end==index){
  82.  
  83. 				if(number_of_open_unbalanced==1){
  84. 					number_of_closed_unbalanced=1;
  85. 					number_of_open_unbalanced=0;
  86. 				}
  87. 				else {
  88. 					number_of_closed_unbalanced=0;
  89. 					number_of_open_unbalanced=1;
  90. 				}
  91. 				//sum=min_sum=min_sum==1?-1:1;
  92. 				return ;
  93. 			}
  94. 			int mid=(start+end)>>1;
  95. 			if(index<=mid)left_child.update(index);
  96. 			else if(index>mid)right_child.update(index);
  97. 			join(this, left_child, right_child);
  98. 		}
  99. 		public static void print_inOrder(Segment_Tree parent){
  100. 			if(parent==null)return;
  101. 			else{
  102. 			print_inOrder(parent.left_child);
  103. 			System.out.println(parent.number_of_open_unbalanced+" "+parent.number_of_closed_unbalanced);
  104. 			print_inOrder(parent.right_child);
  105. 			}
  106. 		}
  107. 		public static void print_postOrder(Segment_Tree parent){
  108. 			if(parent==null)return;
  109. 			else{
  110. 				print_postOrder(parent.left_child);
  111. 				print_postOrder(parent.right_child);
  112. 				System.out.println(parent.number_of_open_unbalanced+" "+parent.number_of_closed_unbalanced);
  113. 			}
  114. 		}
  115. 	}
  116. static class Reader {
  117. 	final private int BUFFER_SIZE = 1 << 16;
  118. 	private DataInputStream din;
  119. 	private byte[] buffer;
  120. 	private int bufferPointer, bytesRead;
  121.  
  122. 	public Reader() {
  123. 		din = new DataInputStream(System.in);
  124. 		buffer = new byte[BUFFER_SIZE];
  125. 		bufferPointer = bytesRead = 0;
  126. 	}
  127.  
  128. 	public Reader(String file_name) throws IOException {
  129. 		din = new DataInputStream(new FileInputStream(file_name));
  130. 		buffer = new byte[BUFFER_SIZE];
  131. 		bufferPointer = bytesRead = 0;
  132. 	}
  133.  
  134. 	public String readLine() throws IOException {
  135. 		byte[] buf = new byte[64];
  136. 		int cnt = 0, c;
  137. 		while ((c = read()) != -1) {
  138. 			if (c == '\n')
  139. 				break;
  140. 			buf[cnt++] = (byte) c;
  141. 		}
  142. 		return new String(buf, 0, cnt);
  143. 	}
  144.  
  145. 	public int nextInt() throws IOException {
  146. 		int ret = 0;
  147. 		byte c = read();
  148. 		while (c <= ' ')
  149. 			c = read();
  150. 		boolean neg = (c == '-');
  151. 		if (neg)
  152. 			c = read();
  153. 		do {
  154. 			ret = ret * 10 + c - '0';
  155. 		} while ((c = read()) >= '0' && c <= '9');
  156. 		if (neg)
  157. 			return -ret;
  158. 		return ret;
  159. 	}
  160.  
  161. 	public long nextLong() throws IOException {
  162. 		long ret = 0;
  163. 		byte c = read();
  164. 		while (c <= ' ')
  165. 			c = read();
  166. 		boolean neg = (c == '-');
  167. 		if (neg)
  168. 			c = read();
  169. 		do {
  170. 			ret = ret * 10 + c - '0';
  171. 		} while ((c = read()) >= '0' && c <= '9');
  172. 		if (neg)
  173. 			return -ret;
  174. 		return ret;
  175. 	}
  176.  
  177. 	public double nextDouble() throws IOException {
  178. 		double ret = 0, div = 1;
  179. 		byte c = read();
  180. 		while (c <= ' ')
  181. 			c = read();
  182. 		boolean neg = (c == '-');
  183. 		if (neg)
  184. 			c = read();
  185. 		do {
  186. 			ret = ret * 10 + c - '0';
  187. 		} while ((c = read()) >= '0' && c <= '9');
  188. 		if (c == '.')
  189. 			while ((c = read()) >= '0' && c <= '9')
  190. 				ret += (c - '0') / (div *= 10);
  191. 		if (neg)
  192. 			return -ret;
  193. 		return ret;
  194. 	}
  195.  
  196. 	private void fillBuffer() throws IOException {
  197. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  198. 		if (bytesRead == -1)
  199. 			buffer[0] = -1;
  200. 	}
  201.  
  202. 	private byte read() throws IOException {
  203. 		if (bufferPointer == bytesRead)
  204. 			fillBuffer();
  205. 		return buffer[bufferPointer++];
  206. 	}
  207.  
  208. 	public void close() throws IOException {
  209. 		if (din == null)
  210. 			return;
  211. 		din.close();
  212. 	}
  213. }
  214.  
  215. }
  216. /*
  217. 12
  218. (()(()(())))
  219. 16
  220. 0
  221. 1
  222. 3
  223. 0
  224. 4
  225. 5
  226. 6
  227. 0
  228. 10
  229. 0
  230. 2
  231. 0
  232. 1
  233. 3
  234. 4
  235. 0
  236. */
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
14
)(()()(()())))
3
0
1
0
stdout
copy 
Test 1:
NO
YES
https://ideone.com/rLBHCt
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!