fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5. //import java.util.TreeMap;
  6.  
  7.  
  8. class GSS1 {
  9. static int segment_tree[];
  10. static int array[];
  11. 	public static void main(String[] args) throws NumberFormatException, IOException {
  12. 		// TODO Auto-generated method stub
  13. BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  14. int N=Integer.parseInt(br.readLine().trim());
  15.  array=new int[N];
  16. StringTokenizer st=new StringTokenizer(br.readLine().trim());
  17. for(int i=0;i<N;i++){
  18. 	array[i]=Integer.parseInt(st.nextToken());
  19. }
  20. segment_tree=new int[4*N];
  21. build(1, 0, N-1);
  22. //for(int i=0;i<2*N;i++)System.out.print(segment_tree[i]+" ");
  23. //System.out.println();
  24. int M=Integer.parseInt(br.readLine().trim());
  25. StringBuilder sb=new StringBuilder();
  26. for(int i=0;i<M;i++){
  27. 	//TreeMap<Integer,Integer> tm=new TreeMap<Integer, Integer>();
  28. 	st=new StringTokenizer(br.readLine().trim());
  29. 	int x=Integer.parseInt(st.nextToken());
  30. 	int y=Integer.parseInt(st.nextToken());
  31. 	int nas=query(1, 0, N-1, x-1, y-1);
  32. 	sb.append(nas+"\n");
  33. }
  34. 	System.out.println(sb);
  35. 	}
  36. public static void build(int node,int a,int b){
  37. 	if(a>b)return;//out of range
  38. 	else if(a==b){
  39. 		segment_tree[node]= array[a];
  40. 		return;
  41. 	}
  42. 	build(node*2, a,(a+b)/2);
  43. 	build(node*2+1, 1+(a+b)/2, b);
  44. 	segment_tree[node]=Math.max(segment_tree[node*2],Math.max(segment_tree[node*2+1],segment_tree[node*2]+segment_tree[node*2+1]));
  45.  
  46. }
  47. public static int query(int node,int a,int b,int i,int j){
  48. 	if(a>j || b<i || a>b)return -1000000000;
  49. 	else if(a>=i && b<=j)return segment_tree[node]; 
  50. 	int q1=query(node*2, a,(a+ b)/2, i, j);
  51. 	int q2=query(node*2+1,1+(a+b)/2,b,i,j);
  52. 	//System.out.println(q1+" "+q2+" "+Math.max(q1, Math.max(q2,q1+q2)));
  53. 	return Math.max(q1, Math.max(q2,q1+q2));
  54. }
  55. }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
6
1 2 79 80 -90 -8
1
1 6
stdout
copy 
162
https://ideone.com/WtT3xh
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!