fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. class FastReader {
  7.     BufferedReader br;
  8.     StringTokenizer st;
  9.  
  10.     public FastReader() {
  11.         br = new BufferedReader(new InputStreamReader(System.in));
  12.     }
  13.  
  14.     String next() throws IOException {
  15.         while (st == null || !st.hasMoreElements()) {
  16.             st = new StringTokenizer(br.readLine());
  17.         }
  18.         return st.nextToken();
  19.     }
  20.  
  21.     int nextInt() throws IOException {
  22.         return Integer.parseInt(next());
  23.     }
  24.  
  25.     long nextLong() throws IOException {
  26.         return Long.parseLong(next());
  27.     }
  28.  
  29.     double nextDouble() throws IOException {
  30.         return Double.parseDouble(next());
  31.     }
  32.  
  33.     String nextLine() throws IOException{
  34.         return br.readLine();
  35.     }
  36. }
  37.  
  38. class Main{
  39.     static class Node{
  40.         long prefix, suffix;
  41.         long max;
  42.         long sum;
  43.         Node(int s){
  44.             prefix = suffix = max = sum = s;
  45.         }
  46.     }
  47.  
  48.     public static void build(int ind, int l, int r){
  49.         if( l==r){
  50.             segment[ind] = new Node(ar[l]);
  51.             return;
  52.         }
  53.         int mid = l+ (r-l)/2;
  54.         build(2*ind+1, l, mid);
  55.         build(2*ind+2, mid+1, r);
  56.  
  57.         segment[ind] = new Node(0);
  58.         calulate(segment[ind], segment[2*ind+1], segment[2*ind+2]);
  59.     }
  60.     public static void calulate(Node res, Node left, Node right){
  61.         res.prefix = Math.max(left.prefix, left.sum+ right.prefix);
  62.         res.suffix = Math.max(right.suffix, right.sum+ left.suffix);
  63.         res.max = Math.max(Math.max(left.max, right.max), left.suffix+right.prefix);
  64.         res.sum = left.sum + right.sum;
  65.         res.max = Math.max(res.max, res.prefix);
  66.         res.max = Math.max(res.max, res.suffix);
  67.         res.max = Math.max(res.max, res.sum);
  68.     }
  69.  
  70.     public static Node query(int ind, int l, int r, int ql, int qr){
  71.         Node res = new Node(0);
  72.         if( r < ql || qr < l){
  73.             return res;
  74.         }
  75.         if( ql <= l && qr >= r){
  76.             return segment[ind];
  77.         }
  78.         int mid = l+ (r-l)/2;
  79.         Node left = query(2*ind+1, l, mid, ql ,qr);
  80.         Node right = query(2*ind+2, mid+1, r, ql ,qr);
  81.         calulate(res, left, right);
  82.         return res;
  83.     }
  84.     static int[] ar;
  85.     static Node[] segment;
  86.     public static void main(String[] args) throws IOException {
  87.         FastReader ff = new FastReader();
  88.         int n = ff.nextInt();
  89.         ar = new int[n];
  90.         segment = new Node[(4*n)+5];
  91.         for(int i = 0; i < n; i++){
  92.             ar[i] = ff.nextInt();
  93.         }
  94.         build(0, 0, n-1);
  95.         int q = ff.nextInt();
  96.  
  97.         while(q-- > 0){
  98.             int l = ff.nextInt()-1;
  99.             int r = ff.nextInt()-1;
  100.             System.out.println(query(0, 0, n - 1, l, r).max);
  101.         }
  102.     }
  103. }
Success #stdin #stdout 0.08s 47808KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/UuWQ3X
problem GSS1, based on SPOJ submission 28093292 (JAVA), 2021-06-22 10:15:53
language:
Java (HotSpot 12)
created:
4 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!