#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
long long int build_sum_seg(long int *ar, long long int *sts, int start, int end, int pos)
{
if(start == end)
return(sts[pos] = ar[start]);
int mid = (start + end)/2;
sts[pos] = build_sum_seg(ar, sts, start, mid, 2 * pos + 1) + build_sum_seg(ar, sts, mid + 1, end, 2 * pos + 2);
}
long long int find_sum(long long int *sts, int start, int end, int qstart, int qend, int pos)
{
if(start > qend or qstart > end or start > end)
return 0;
else if(qstart <= start and end <= qend)
return sts[pos];
int mid = (start + end)/2;
return ( find_sum(sts, start, mid, qstart, qend, 2 * pos + 1) + find_sum(sts, mid + 1, end, qstart, qend, 2 * pos + 2) );
}
void update_sum(long long int *sts, int start, int end, int pos, int index, long int diff)
{
if(index < start or index > end or start > end)
return;
sts[pos] = sts[pos] + diff;
int mid = (start + end)/2;
if(start != end)
{
update_sum(sts, start, mid, 2 * pos + 1, index, diff);
update_sum(sts, mid + 1, end, 2 * pos + 2, index, diff);
}
}
long long int *create_sum_seg(int n)
{
int x = ceil((log2(n)));
int size = 2 * int(pow(2,x)) - 1;
return new long long int[size];
}
long int build_min_seg(long int *ar, long int *stm, int start, int end, int pos)
{
if(start == end)
return(stm[pos] = ar[start]);
int mid = (start + end)/2;
stm[pos] = min( build_min_seg(ar, stm, start, mid, 2 * pos + 1), build_min_seg(ar, stm, mid + 1, end, 2 * pos + 2) );
}
long int find_min(long int *stm, int start, int end, int qstart, int qend, int pos)
{
if(start > qend or qstart > end or start > end)
return 1000000001;
else if(qstart <= start and end <= qend)
return stm[pos];
int mid = (start + end)/2;
return (min( find_min(stm, start, mid, qstart, qend, 2 * pos + 1), find_min(stm, mid + 1, end, qstart, qend, 2 * pos + 2) ));
}
void update_min(long int *stm, int start, int end, int pos, int index, long int diff)
{
if(index < start or index > end or start > end)
return;
else if(start == end)
stm[pos] = stm[pos] + diff;
else
{
int mid = (start + end)/2;
update_min(stm, start, mid, 2 * pos + 1, index, diff);
update_min(stm, mid + 1, end, 2 * pos + 2, index, diff);
stm[pos] = min(stm[2*pos+1],stm[2*pos+2]);
}
}
long int *create_min_seg(int n)
{
int x = ceil((log2(n)));
int size = 2 * int(pow(2,x)) - 1;
return new long int[size];
}
int main()
{
int n, q;
scanf("%d",&n);
long int *ar = new long int[n], *stm = create_min_seg(n);
long long int *sts = create_sum_seg(n);
for(int i = 0; i < n; ++i)
scanf("%d",&ar[i]);
build_min_seg(ar, stm, 0, n - 1, 0); build_sum_seg(ar, sts, 0, n - 1, 0);
scanf("%d",&q);
while(q--)
{
char str[7];
int x, y;
scanf("%s%d%d",str,&x,&y);
if(strcmp(str,"COUNT") == 0)
printf("%d\n", ( find_sum(sts, 0, n - 1, x, y, 0) - find_min(stm, 0, n -1 , x, y, 0) ) );
else if(strcmp(str,"GROW") == 0)
{
ar[y] += x;
update_min(stm, 0, n - 1, 0, y, x);
update_sum(sts, 0, n - 1, 0, y, x);
}
else
{
ar[y] -= x;
update_min(stm, 0, n - 1, 0, y, -x);
update_sum(sts, 0, n - 1, 0, y, -x);
}
}
}
`
It is giving WA but all test cases passes from SPOJ Toolkit on my system