fork(2) download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.util.Comparator;
  7.  
  8.  
  9. class GSS2 {
  10. static int a[];
  11. static int pos[];
  12. 	public static void main(String[] args) throws IOException {
  13. 		// TODO Auto-generated method stub
  14. 		pos=new int[200002];
  15. Reader r=new Reader();
  16. StringBuilder sb=new StringBuilder();
  17. PrintWriter pr=new PrintWriter(System.out); 
  18. int n=r.nextInt();
  19. a=new int[n+1];
  20. Segment_Tree st=new Segment_Tree(1,n);
  21. for(int i=1;i<=n;i++)a[i]=r.nextInt();
  22. int q=r.nextInt();
  23. int queries[][]=new int[q][3];
  24. long answers[][]=new long[q][2];
  25. for(int i=0;i<q;i++){
  26. 	answers[i][0]=i;
  27. 	queries[i][0]=i;
  28. 	queries[i][1]=r.nextInt();
  29. 	queries[i][2]=r.nextInt();
  30. }
  31. Arrays.sort(queries,new Comparator<int []>() {
  32.  
  33. 	@Override
  34. 	public int compare(int[] o1, int[] o2) {
  35. 		// TODO Auto-generated method stub
  36. 		return Integer.valueOf(o1[2]-o2[2]);
  37. 	}
  38. });
  39. int j=1;
  40. for(int i=0;i<q;i++){
  41. 	while(j<=queries[i][2]){
  42. 		if(pos[a[j]+100000]==0){
  43. 			st.update(j);
  44. 			pos[a[j]+100000]=j;
  45. 		}
  46. 		else{
  47. 			st.update(pos[a[j]+100000]);
  48. 			pos[a[j]+100000]=j;
  49. 			st.update(j);
  50. 		}
  51. 		j++;
  52. 	}
  53. 	long ans=st.query(queries[i][1],queries[i][2]).bestsum;
  54. 	answers[queries[i][0]][1]=ans<0?0:ans;
  55. }
  56. 	Arrays.sort(answers,new Comparator<long []>() {
  57.  
  58. 		@Override
  59. 		public int compare(long[] o1, long[] o2) {
  60. 			// TODO Auto-generated method stub
  61. 			return Integer.valueOf((int) (o1[0]-o2[0]));
  62. 		}
  63. 	});
  64. 	for(int i=0;i<q;i++){
  65. 		sb.append(answers[i][1]+"\n");
  66. 	}
  67. 	pr.write(sb.toString());
  68. 	pr.flush();
  69. 	}
  70. 	static class Segment_Tree{
  71. 		int start,end;
  72. 		Segment_Tree left_child,right_child;
  73. 		long bestleftsum,bestrightsum,bestsum,sum;
  74. 		int value;
  75. 		public Segment_Tree() {}
  76. 		public Segment_Tree(int a,int b){
  77. 			start=a;end=b;
  78. 			if(start!=end){
  79. 				int mid=(start+end)>>1;
  80. 				left_child=new Segment_Tree(a,mid);
  81. 				right_child=new Segment_Tree(mid+1, b);
  82. 				join(this,left_child,right_child);
  83. 			}
  84. 			else{
  85. 				bestleftsum=bestrightsum=bestsum=sum=GSS2.a[start];
  86. 			}
  87. 		}
  88. 		public static void join(Segment_Tree parent,Segment_Tree left_child,Segment_Tree right_child){
  89. 			parent.sum=left_child.sum+right_child.sum;
  90. 			parent.bestleftsum=Math.max(left_child.bestleftsum, left_child.sum+right_child.bestleftsum);
  91. 			parent.bestrightsum=Math.max(right_child.bestrightsum,right_child.sum+left_child.bestrightsum);
  92. 			parent.bestsum=Math.max(left_child.bestsum,Math.max(right_child.bestsum,left_child.bestrightsum+right_child.bestleftsum));
  93. 		}
  94. 		public void update(int i){
  95. 			if(i>end || i<start)return;
  96. 			if(start==i && end==i){
  97. 				if(value==0){
  98. 					value=1;
  99. 					bestleftsum=bestrightsum=bestsum=sum=GSS2.a[i];
  100. 					}
  101. 				else {
  102. 					value=0;
  103. 					bestleftsum=bestrightsum=bestsum=sum=0;
  104. 				}
  105. 				return;
  106. 			}
  107. 			int mid=(start+end)>>1;
  108. 			if(i>mid)right_child.update(i);
  109. 			else if(i<=mid)left_child.update(i);
  110. 			join(this,left_child,right_child);
  111. 		}
  112. 		public Segment_Tree query(int a,int b){
  113. 			if(a>b || a>end || b<start)return null;
  114. 			if(start==a && end==b)return this;
  115. 			int mid=(start+end)>>1;
  116. 			if(a>mid)return right_child.query(a, b);
  117. 			else if(b<=mid)return left_child.query(a, b);
  118. 			Segment_Tree ans=new Segment_Tree();
  119. 			join(ans,left_child.query(a,mid),right_child.query(mid+1, b));
  120. 			return ans;
  121. 		}
  122. 	}
  123. static class Reader {
  124. 	final private int BUFFER_SIZE = 1 << 16;
  125. 	private DataInputStream din;
  126. 	private byte[] buffer;
  127. 	private int bufferPointer, bytesRead;
  128.  
  129. 	public Reader() {
  130. 		din = new DataInputStream(System.in);
  131. 		buffer = new byte[BUFFER_SIZE];
  132. 		bufferPointer = bytesRead = 0;
  133. 	}
  134.  
  135. 	public Reader(String file_name) throws IOException {
  136. 		din = new DataInputStream(new FileInputStream(file_name));
  137. 		buffer = new byte[BUFFER_SIZE];
  138. 		bufferPointer = bytesRead = 0;
  139. 	}
  140.  
  141. 	public String readLine() throws IOException {
  142. 		byte[] buf = new byte[64];
  143. 		int cnt = 0, c;
  144. 		while ((c = read()) != -1) {
  145. 			if (c == '\n')
  146. 				break;
  147. 			buf[cnt++] = (byte) c;
  148. 		}
  149. 		return new String(buf, 0, cnt);
  150. 	}
  151.  
  152. 	public int nextInt() throws IOException {
  153. 		int ret = 0;
  154. 		byte c = read();
  155. 		while (c <= ' ')
  156. 			c = read();
  157. 		boolean neg = (c == '-');
  158. 		if (neg)
  159. 			c = read();
  160. 		do {
  161. 			ret = ret * 10 + c - '0';
  162. 		} while ((c = read()) >= '0' && c <= '9');
  163. 		if (neg)
  164. 			return -ret;
  165. 		return ret;
  166. 	}
  167.  
  168. 	public long nextLong() throws IOException {
  169. 		long ret = 0;
  170. 		byte c = read();
  171. 		while (c <= ' ')
  172. 			c = read();
  173. 		boolean neg = (c == '-');
  174. 		if (neg)
  175. 			c = read();
  176. 		do {
  177. 			ret = ret * 10 + c - '0';
  178. 		} while ((c = read()) >= '0' && c <= '9');
  179. 		if (neg)
  180. 			return -ret;
  181. 		return ret;
  182. 	}
  183.  
  184. 	public double nextDouble() throws IOException {
  185. 		double ret = 0, div = 1;
  186. 		byte c = read();
  187. 		while (c <= ' ')
  188. 			c = read();
  189. 		boolean neg = (c == '-');
  190. 		if (neg)
  191. 			c = read();
  192. 		do {
  193. 			ret = ret * 10 + c - '0';
  194. 		} while ((c = read()) >= '0' && c <= '9');
  195. 		if (c == '.')
  196. 			while ((c = read()) >= '0' && c <= '9')
  197. 				ret += (c - '0') / (div *= 10);
  198. 		if (neg)
  199. 			return -ret;
  200. 		return ret;
  201. 	}
  202.  
  203. 	private void fillBuffer() throws IOException {
  204. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  205. 		if (bytesRead == -1)
  206. 			buffer[0] = -1;
  207. 	}
  208.  
  209. 	private byte read() throws IOException {
  210. 		if (bufferPointer == bytesRead)
  211. 			fillBuffer();
  212. 		return buffer[bufferPointer++];
  213. 	}
  214.  
  215. 	public void close() throws IOException {
  216. 		if (din == null)
  217. 			return;
  218. 		din.close();
  219. 	}
  220. }
  221.  
  222. }
  223. /*
  224. 9
  225. 1 2 1 2 3 4 3 4 5
  226. 5
  227. 1 2
  228. 1 4
  229. 1 6
  230. 1 8
  231. 1 9
  232. */
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
9
1 2 1 2 3 -4 3 4 5
5
1 2
1 4
1 6
1 8
1 9
stdout
copy 
3
3
6
7
12
https://ideone.com/4KLJrL
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!