fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.IOException;
  3.  
  4. class GSS1NODE {
  5.     public static void main(String args[])throws IOException {
  6.         Reader s = new Reader();
  7.         final int N = s.nextInt();
  8.         int input[] = new int[N];
  9.         for (int i = 0; i < N; i++) {
  10.             input[i] = s.nextInt();
  11.         }
  12.         GSS1NODE obj=new GSS1NODE();
  13.         obj.buildUtility(input);
  14.     }
  15.     void buildUtility(int input[])throws IOException{
  16.         GSS1NODE obj=new GSS1NODE();
  17.         int len=input.length;
  18.         int maxSize=2*(int)Math.pow(2,(int)Math.ceil(Math.log(len)/Math.log(2)))-1;
  19.         Node segTree[]=new Node[maxSize];
  20.  
  21.         for (int i = 0; i <maxSize ; i++) {
  22.             segTree[i]=new Node();
  23.         }
  24.  
  25.         obj.buildTree(input,0,len-1,0,segTree);
  26.  
  27.         /*System.out.println();
  28.         for (int i = 0; i <maxSize ; i++) {
  29.             System.out.print(segTree[i].B+" ");
  30.         }*/
  31.  
  32.         Reader s = new Reader();
  33.         int M = s.nextInt();
  34.         while (M-- > 0) {
  35.             Node temp=obj.query(s.nextInt() - 1, s.nextInt() - 1, 0, len- 1, 0,segTree);
  36.             System.out.println(temp.B);
  37.         }
  38.     }
  39.     void buildTree(int input[],int low,int high,int pos,Node segTree[]){
  40.         if(low>high)
  41.             return;
  42.         if(low==high){
  43.             Node newNode=new Node();
  44.             newNode.B=input[low];
  45.             newNode.L=input[low];
  46.             newNode.R=input[low];
  47.             newNode.T=input[low];
  48.             segTree[pos]=newNode;
  49.             return;
  50.         }
  51.         GSS1NODE obj=new GSS1NODE();
  52.         int mid=(low+high)/2;
  53.         int left=pos*2+1,right=pos*2+2;
  54.         buildTree(input,low,mid,left,segTree);
  55.         buildTree(input,mid+1,high,right,segTree);
  56.         segTree[pos]=obj.join(segTree[left],segTree[right]);
  57.     }
  58.  
  59.     Node join(Node left,Node right){
  60.         GSS1NODE obj=new GSS1NODE();
  61.         Node newNode=new Node();
  62.         newNode.L=Math.max(left.L,left.T+right.L);
  63.         newNode.R=Math.max(left.R+right.T,right.R);
  64.         newNode.T=left.T+right.T;
  65.         newNode.B=obj.max3(left.B,right.B,left.R+right.L);
  66.         return newNode;
  67.     }
  68.     Node query(int qlow,int qhigh,int low,int high,int pos,Node segTree[]){
  69.         //no overlap
  70.         if(qlow>high || low>qhigh){
  71.             return new Node();
  72.         }
  73.  
  74.         //total overlap
  75.         if(low>=qlow && high<=qhigh)
  76.             return segTree[pos];
  77.  
  78.         //partial overlap
  79.         GSS1NODE obj=new GSS1NODE();
  80.         int mid=(low+high)/2;
  81.         int left=pos*2+1,right=pos*2+2;
  82.         return obj.join(query(qlow,qhigh,low,mid,left,segTree),query(qlow,qhigh,mid+1,high,right,segTree));
  83.     }
  84.     int max3(int a,int b,int c){
  85.         return Math.max(a,Math.max(b,c));
  86.     }
  87.     class Node{
  88.         int L,R,T,B;
  89.         Node(){
  90.             L=-15008;
  91.             R=-15008;
  92.             T=-15008;
  93.             B=-15008;
  94.         }
  95.     }
  96.     static class Reader
  97.     {
  98.         final private int BUFFER_SIZE = 1 << 16;
  99.         private DataInputStream din;
  100.         private byte[] buffer;
  101.         private int bufferPointer, bytesRead;
  102.  
  103.         public Reader()
  104.         {
  105.             din = new DataInputStream(System.in);
  106.             buffer = new byte[BUFFER_SIZE];
  107.             bufferPointer = bytesRead = 0;
  108.         }
  109.  
  110.         public String readLine() throws IOException
  111.         {
  112.             byte[] buf = new byte[64]; // line length
  113.             int cnt = 0, c;
  114.             while ((c = read()) != -1)
  115.             {
  116.                 if (c == '\n')
  117.                     break;
  118.                 buf[cnt++] = (byte) c;
  119.             }
  120.             return new String(buf, 0, cnt);
  121.         }
  122.  
  123.         public int nextInt() throws IOException
  124.         {
  125.             int ret = 0;
  126.             byte c = read();
  127.             while (c <= ' ')
  128.                 c = read();
  129.             boolean neg = (c == '-');
  130.             if (neg)
  131.                 c = read();
  132.             do
  133.             {
  134.                 ret = ret * 10 + c - '0';
  135.             }  while ((c = read()) >= '0' && c <= '9');
  136.  
  137.             if (neg)
  138.                 return -ret;
  139.             return ret;
  140.         }
  141.  
  142.         private void fillBuffer() throws IOException
  143.         {
  144.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  145.             if (bytesRead == -1)
  146.                 buffer[0] = -1;
  147.         }
  148.  
  149.         private byte read() throws IOException
  150.         {
  151.             if (bufferPointer == bytesRead)
  152.                 fillBuffer();
  153.             return buffer[bufferPointer++];
  154.         }
  155.     }
  156. }
  157.  
Runtime error #stdin #stdout #stderr 0.05s 4386816KB
comments (?)
stdin
copy 
3
-1507 -1507 -1507
3
1 2
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 65536
	at GSS1NODE$Reader.read(Main.java:153)
	at GSS1NODE$Reader.nextInt(Main.java:128)
	at GSS1NODE.buildUtility(Main.java:33)
	at GSS1NODE.main(Main.java:13)
https://ideone.com/KiFKcC
problem GSS1, based on SPOJ submission 19885646 (JAVA), 2017-07-30 07:32:43
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!