I had a code accepted for GSS3.and i used the same code for gss1 with slight modifications.but its giving me WA.i tried lot of cases on the forum each gives a correct answer.can anyone please help me out here
/*
*************************************************************************
* $ Author : honeyslawyer $
* $ Name : shashank gupta $
*************************************************************************
*
* Copyright 2013 @ honeyslawyer and shashank gupta
*
************************************************************************/
#include<cstdio>
#include<iostream>
#include<cmath>
//#include<conio.h>
#include<cstring>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<string>
#include<climits>
#define mod 1000000007
#define ll long long
#define gc getchar_unlocked
using namespace std;
ll gcd(ll a,ll b) {if(b==0) return a; return gcd(b,a%b);}
void scan(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
ll power(ll b,ll exp,ll m)
{ll ans=1;
b%=m;
while(exp)
{if(exp&1)
ans=(ans*b)%m;
exp>>=1;
b=(b*b)%m;
}
return ans;
}
int n;
struct node
{
int segmentSum,bestPrefix,bestSuffix,bestSum;
node split(node& l, node& r){}
node merge(node& l, node& r)
{
segmentSum = l.segmentSum + r.segmentSum;
bestPrefix = max( l.segmentSum + r.bestPrefix , l.bestPrefix );
bestSuffix = max( r.segmentSum + l.bestSuffix , r.bestSuffix );
bestSum = max( max( l.bestSum , r.bestSum) , l.bestSuffix + r.bestPrefix );
}
};
struct node tree[1000020];
node createleaf(int val)//the leaf nodes, which represent a single element of the array, will be created in this manner
{
node n;
n.segmentSum = n.bestPrefix = n.bestSuffix = n.bestSum = val;
return n;
}
//range_query and update function remain same as that for last problem
node range_query(int root, int left_most_leaf, int right_most_leaf, int u, int v)
{
//query the interval [u,v), ie, {x:u<=x<v}
//the interval [left_most_leaf,right_most_leaf) is
//the set of all leaves descending from "root"
if(u<=left_most_leaf && right_most_leaf<=v)
return tree[root];
int mid = (left_most_leaf+right_most_leaf)/2,
left_child = root*2,
right_child = left_child+1;
tree[root].split(tree[left_child], tree[right_child]);
node l=createleaf(-10000-1), r=createleaf(-10000-1);
//identity is an element such that merge(x,identity) = merge(identity,x) = x for all x
if(u < mid) l = range_query(left_child, left_most_leaf, mid, u, v);
if(v > mid) r = range_query(right_child, mid, right_most_leaf, u, v);
tree[root].merge(tree[left_child],tree[right_child]);
node n;
n.merge(l,r);
return n;
}
void mergeup(int postn)
{
postn >>=1;
while(postn>0)
{
tree[postn].merge(tree[postn*2],tree[postn*2+1]);
postn >>=1;
}
}
void update(int pos, node new_val)
{
pos+=(1<<n);
tree[pos]=new_val;
mergeup(pos);
}
int a[100000];
int create()
{
int m;
//scanf("%d",&m);
scan(m);
n=(int)log2(double(2*m-1));
for(int i=0;i<m;i++)
scan(a[i]);
//scanf("%d",&a[i]);
// put appropriate values at each leaf
for(int i=0; i<(1<<n); i++)
tree[i+(1<<n)] = createleaf(a[i]);
// update all internal nodes in bottom up fashion
for(int i=(1<<n)-1; i; i--)
tree[i].merge(tree[i*2], tree[i*2+1]);
}
int main()
{
create();
int t;
//scanf("%d",&t);
scan(t);
while(t--)
{
int a,x,y;
//scanf("%d %d %d",&a,&x,&y);
//scan(a);
a=1;
scan(x);
scan(y);
if(a==0)
{
node z=createleaf(y);
update(x-1,z);
}
else
{
struct node z=range_query(1,1<<n,1<<(n+1),(1<<n)+x-1,(1<<n)+y);
cout<<z.bestSum<<endl;
}
}
//getch();
return 0;
/*checklist
1)getch() and conio.h removed.*/
}