fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. class Reader {
  6.     final private int BUFFER_SIZE = 1 << 16;
  7.     private DataInputStream din;
  8.     private byte[] buffer;
  9.     private int bufferPointer, bytesRead;
  10.  
  11.     public Reader()
  12.     {
  13.         din = new DataInputStream(System.in);
  14.         buffer = new byte[BUFFER_SIZE];
  15.         bufferPointer = bytesRead = 0;
  16.     }
  17.  
  18.     public int nextInt() throws IOException
  19.     {
  20.         int ret = 0;
  21.         byte c = read();
  22.         while (c <= ' ') {
  23.             c = read();
  24.         }
  25.         boolean neg = (c == '-');
  26.         if (neg)
  27.             c = read();
  28.         do {
  29.             ret = ret * 10 + c - '0';
  30.         } while ((c = read()) >= '0' && c <= '9');
  31.  
  32.         if (neg)
  33.             return -ret;
  34.         return ret;
  35.     }
  36.     private void fillBuffer() throws IOException
  37.     {
  38.         bytesRead = din.read(buffer, bufferPointer = 0,
  39.                 BUFFER_SIZE);
  40.         if (bytesRead == -1)
  41.             buffer[0] = -1;
  42.     }
  43.  
  44.     private byte read() throws IOException
  45.     {
  46.         if (bufferPointer == bytesRead)
  47.             fillBuffer();
  48.         return buffer[bufferPointer++];
  49.     }
  50. }
  51.  
  52. class Main{
  53.     static class Node{
  54.         long prefix, suffix;
  55.         long max;
  56.         long sum;
  57.         Node(){
  58.             prefix = suffix = max = sum = -15008;
  59.         }
  60.         Node(int s){
  61.             prefix = suffix = max = sum = s;
  62.         }
  63.     }
  64.  
  65.     public static void build(int ind, int l, int r){
  66.         if( l==r){
  67.             segment[ind] = new Node(ar[l]);
  68.             return;
  69.         }
  70.         int mid = l+ (r-l)/2;
  71.         build(2*ind+1, l, mid);
  72.         build(2*ind+2, mid+1, r);
  73.  
  74.         segment[ind] = new Node();
  75.         calulate(segment[ind], segment[2*ind+1], segment[2*ind+2]);
  76.     }
  77.     public static void calulate(Node res, Node left, Node right){
  78.         res.prefix = Math.max(left.prefix, left.sum+ right.prefix);
  79.         res.suffix = Math.max(right.suffix, right.sum+ left.suffix);
  80.         res.sum = left.sum + right.sum;
  81.         res.max = Math.max(left.max, right.max);
  82.         res.max = Math.max(res.max, left.suffix+right.prefix);
  83.     }
  84.  
  85.     public static Node query(int ind, int l, int r, int ql, int qr){
  86.         Node res = new Node();
  87.         if( r < ql || qr < l){
  88.             return res;
  89.         }
  90.         if( ql <= l && qr >= r){
  91.             return segment[ind];
  92.         }
  93.         int mid = l+ (r-l)/2;
  94.         if(ql>mid)
  95.             return query(2 * ind + 2, mid + 1, r, ql, qr);
  96.  
  97.         else if(qr<=mid)
  98.             return query(2 * ind + 1, l, mid, ql, qr);
  99.         else {
  100.             Node left = query(2 * ind + 1, l, mid, ql, qr);
  101.             Node right = query(2 * ind + 2, mid + 1, r, ql, qr);
  102.             calulate(res, left, right);
  103.             return res;
  104.         }
  105.     }
  106.     static int[] ar;
  107.     static Node[] segment;
  108.     public static void main(String[] args) throws IOException {
  109.         Reader ff = new Reader();
  110.         int n = ff.nextInt();
  111.         ar = new int[n];
  112.         segment = new Node[(4*n)+5];
  113.         for(int i = 0; i < n; i++){
  114.             ar[i] = ff.nextInt();
  115.         }
  116.         build(0, 0, n-1);
  117.         int q = ff.nextInt();
  118.  
  119.         while(q-- > 0){
  120.             int l = ff.nextInt()-1;
  121.             int r = ff.nextInt()-1;
  122.             System.out.println(query(0, 0, n - 1, l, r).max);
  123.         }
  124.     }
  125. }
Success #stdin #stdout 0.06s 51120KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/JE4pQL
problem GSS1, based on SPOJ submission 28093943 (JAVA), 2021-06-22 12:41:15
language:
Java (HotSpot 12)
created:
2 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!