fork(1) download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. class utkarsh {
  6.  
  7.     InputStream is;
  8.     PrintWriter out;
  9.  
  10.     class node{
  11.         int SUM, P, M, S, B;
  12.         node(int h){
  13.             SUM = P = M = S = B = h;
  14.         }
  15.     }
  16.  
  17.     int a[], n;
  18.     node tree[];
  19.  
  20.     int max(int x, int y){
  21.         return x > y ? x : y;
  22.     }
  23.  
  24.     void build(int N, int s, int e){
  25.         if(s == e){
  26.             tree[N] = new node(a[s]);
  27.             return;
  28.         }
  29.         int mid, lc, rc;
  30.         mid = s + (e - s) / 2;
  31.         lc = 2 * N + 1;
  32.         rc = 2 * N + 2;
  33.         build(lc, s, mid);
  34.         build(rc, mid + 1, e);
  35.         tree[N] = new node(0);
  36.         tree[N].SUM = tree[lc].SUM + tree[rc].SUM;
  37.         tree[N].P = max(tree[lc].P, tree[lc].SUM + tree[rc].P);
  38.         tree[N].M = tree[lc].S + tree[rc].P;
  39.         tree[N].S = max(tree[rc].S, tree[rc].SUM + tree[lc].S);
  40.         tree[N].B = max(tree[N].SUM, max(tree[N].P, max(tree[N].M, max(tree[N].S, max(tree[lc].B, tree[rc].B)))));
  41.     }
  42.  
  43.     node query(int N, int s, int e, int l, int r){
  44.         if(s > r || l > e){
  45.             return new node(-200100);
  46.         }
  47.         if(s >= l && e <= r){
  48.             return tree[N];
  49.         }
  50.         int mid = s + (e - s) / 2;
  51.         if(r <= mid){
  52.             return query(2*N + 1, s, mid, l, r);
  53.         }else if(l > mid){
  54.             return query(2*N + 2, mid + 1, e, l, r);
  55.         }else{
  56.             node LC, RC, disha;
  57.             LC = query(2*N + 1, s, mid, l, r);
  58.             RC = query(2*N + 2, mid + 1, e, l, r);
  59.             disha = new node(0);
  60.             disha.SUM = LC.SUM + RC.SUM;
  61.             disha.P = max(LC.P, LC.SUM + RC.P);
  62.             disha.M = LC.S + RC.P;
  63.             disha.S = max(RC.S, RC.SUM + LC.S);
  64.             disha.B = max(disha.SUM, max(disha.P, max(disha.M, max(disha.S, max(LC.B, RC.B)))));
  65.             return disha;
  66.         }
  67.     }
  68.  
  69.     void solve(){
  70.         //Enter code here utkarsh
  71.         int i, q;
  72.         n = ni();
  73.         a = new int[n];
  74.         tree = new node[4 * n];
  75.         for(i = 0; i < n; i++){
  76.             a[i] = ni();
  77.         }
  78.         build(0, 0, n-1);
  79.         q = ni();
  80.         while(q-- > 0){
  81.             out.println(query(0, 0, n-1, ni() - 1, ni() - 1).B);
  82.         }
  83.     }
  84.  
  85.     public static void main(String[] args) { new utkarsh().run();
  86.     }
  87.     void run(){ is = System.in; out = new PrintWriter(System.out); solve(); out.flush();
  88.     }
  89.  
  90.     byte input[] = new byte[1024];
  91.     int len = 0, ptr = 0;
  92.  
  93.     int readByte(){ if(ptr >= len){ ptr = 0; try{ len = is.read(input); }catch(IOException e){ throw new InputMismatchException(); } if(len <= 0){ return -1; } } return input[ptr++];
  94.     }
  95.     boolean isSpaceChar(int c){ return !( c >= 33 && c <= 126 ); 
  96.     }
  97.     int skip(){ int b = readByte(); while(b != -1 && isSpaceChar(b)){ b = readByte(); } return b;
  98.     }
  99.     int ni(){ int n = 0,b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } if(b == -1){ return -1; } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
  100.     }
  101.     long nl(){ long n = 0L; int b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
  102.     }
  103. }
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/WERmA4
language:
Java (HotSpot 12)
created:
7 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!