fork(1) download
copy 
  1. import java.io.*;
  2. public class Main {private static long[] a;  private static class T {
  3.         long f,g,h;
  4.         void assign(long val)
  5.         {
  6.             if(val<0)
  7.                val=0;
  8.             this.f=val;
  9.             this.g=val;
  10.             this.h=this.f-this.g;
  11.         }
  12.  
  13.         public void merge(T l, T r) {
  14.             this.f=l.f+r.f;
  15.             this.g=Math.min(l.g,r.g);
  16.             this.h=this.f-this.g;
  17.         }
  18.     }
  19.     private static T seg[];
  20.  
  21.     public static void main(String asd[]) throws Exception {
  22.  
  23.         Parser in = new Parser(System.in);
  24.         int n=in.nextInt();
  25.         a=new long[n];
  26.         for(int i=0;i<n;i++)
  27.         {
  28.             a[i]=in.nextLong();
  29.         }
  30.         int tS=1;
  31.         for(;tS<n;tS*=2);
  32.         tS*=2;
  33.         seg=new T[tS];
  34.         for(int i=1;i<tS;i++)
  35.         {
  36.             seg[i]=new T();
  37.         }
  38.         bT(1,0,n-1);
  39.         StringBuilder s,ans=new StringBuilder("");
  40.         int m=in.nextInt();
  41.  
  42.         for(int i=0;i<m;i++)
  43.         {
  44.             s=new StringBuilder(in.next());
  45.             long x=in.nextLong();
  46.             int y=in.nextInt();
  47.             if(s.charAt(0)=='E')
  48.             {
  49.                 x=0-x;
  50.                 uT(1,0,n-1,y,x);
  51.             }
  52.             else if(s.charAt(0)=='G')
  53.             {
  54.                 uT(1,0,n-1,y,x);
  55.             }
  56.             else
  57.             {
  58.                 ans.append(gT(n,x,y)).append("\n");
  59.             }
  60.  
  61.         }
  62.         System.out.print(ans);
  63.     }
  64.  
  65.  
  66.  
  67.     private static long gT(int n,long x, int y) {
  68.         T result=gT(1,0,n-1,x,y);
  69.         return result.h;
  70.     }
  71.  
  72.     private static T gT(int curr, int lS,int rS, long q1, int q2) {
  73.         if(lS==q1 && rS==q2)
  74.         {
  75.             return seg[curr];
  76.         }
  77.         int mid=(lS+rS)>>1,l=curr<<1,r=l+1;
  78.         if(mid<q1)
  79.         {
  80.             return gT(r,mid+1,rS,q1,q2);
  81.         }
  82.         if(q2<=mid)
  83.         {
  84.             return gT(l,lS,mid,q1,q2);
  85.         }
  86.         T left=gT(l,lS,mid,q1,mid);
  87.         T right=gT(r,mid+1,rS,mid+1,q2);
  88.         T res=new T();
  89.         res.merge(left,right);
  90.  
  91.         return res;
  92.     }
  93.  
  94.     private static void uT(int curr, int lS, int rS, int idx, long val) {
  95.         if(lS==rS)
  96.         {
  97.             seg[curr].assign(seg[curr].f+val);
  98.             return;
  99.         }
  100.         int mid=(lS+rS)>>1,l=curr<<1,r=l+1;
  101.         if(mid<idx)
  102.         {
  103.             uT(r,mid+1,rS,idx,val);
  104.         }
  105.         else
  106.         {
  107.             uT(l,lS,mid,idx,val);
  108.         }
  109.         seg[curr].merge(seg[l],seg[r]);
  110.     }
  111.  
  112.     private static void bT(int curr, int lS, int rS) {
  113.         if(lS==rS)
  114.         {
  115.             seg[curr].assign(a[lS]);
  116.             return;
  117.         }
  118.         int mid=(lS+rS)>>1,l=curr<<1,r=l+1;
  119.         bT(l,lS,mid);
  120.         bT(r,mid+1,rS);
  121.         seg[curr].merge(seg[l],seg[r]);
  122.     }
  123.  
  124.  
  125. }
  126.  
  127. class Parser {
  128.     final private int BUFFER_SIZE = 1 << 16;
  129.  
  130.     private DataInputStream din;
  131.     private byte[] buffer;
  132.     private int bufferPointer, bytesRead;
  133.  
  134.     public Parser(InputStream in) {
  135.         din = new DataInputStream(in);
  136.         buffer = new byte[BUFFER_SIZE];
  137.         bufferPointer = bytesRead = 0;
  138.     }
  139.  
  140.     public long nextLong() throws Exception {
  141.         long ret = 0;
  142.         byte c = read();
  143.         while (c <= ' ') c = read();
  144.         boolean neg = c == '-';
  145.         if (neg) c = read();
  146.         do {
  147.             ret = ret * 10 + c - '0';
  148.             c = read();
  149.         } while (c > ' ');
  150.         if (neg) return -ret;
  151.         return ret;
  152.     }
  153.  
  154.     //reads in the next string
  155.     public String next() throws Exception {
  156.         StringBuilder ret = new StringBuilder();
  157.         byte c = read();
  158.         while (c <= ' ') c = read();
  159.         do {
  160.             ret = ret.append((char) c);
  161.             c = read();
  162.         } while (c > ' ');
  163.         return ret.toString();
  164.     }
  165.  
  166.     public int nextInt() throws Exception {
  167.         int ret = 0;
  168.         byte c = read();
  169.         while (c <= ' ') c = read();
  170.         boolean neg = c == '-';
  171.         if (neg) c = read();
  172.         do {
  173.             ret = ret * 10 + c - '0';
  174.             c = read();
  175.         } while (c > ' ');
  176.         if (neg) return -ret;
  177.         return ret;
  178.     }
  179.  
  180.     private void fillBuffer() throws Exception {
  181.         bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  182.         if (bytesRead == -1) buffer[0] = -1;
  183.     }
  184.  
  185.     private byte read() throws Exception {
  186.         if (bufferPointer == bytesRead) fillBuffer();
  187.         return buffer[bufferPointer++];
  188.     }
  189. }
  190.  
  191.  
  192.  
Success #stdin #stdout 0.09s 320576KB
comments (?)
stdin
copy 
10
6 5 12 48 3 20 4 2 3 20
7
COUNT 0 9
EAT 6 9
COUNT 0 9
GROW 12 4
COUNT 0 9
EAT 6 9
COUNT 0 9
stdout
copy 
121
115
127
121
https://ideone.com/FGSlvr
problem COURAGE, based on SPOJ submission 16639898 (JAVA), 2016-03-31 13:10:19
language:
Java (HotSpot 12)
created:
8 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!