problem link:maximum sum from spoj [problem:http://www.spoj.com/problems/KGSS]
my code:
#include<bits/stdc++.h>
using namespace std;
#define mx 100009
#define ll long long int
ll arr[mx];
//ll tree[mx*4];
//ll state=0;
struct nd{
ll high;
ll sum;
};
nd tree[mx*4];
ll ans=-1;
ll res;
void init(ll node,ll l,ll r){
if(l==r){
tree[node].high=arr[l]; //cout<<"lf node:"<<node<<" val:"<<tree[node].high<<endl;
tree[node].sum=arr[l];
return;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
init(Left,l,mid);
init(Right,mid+1,r);
tree[node].high=max(tree[Left].high,tree[Right].high);
ll hh=-1;
hh=max(hh,tree[Left].high+tree[Right].high);
hh=max(hh,tree[Left].sum);
hh=max(hh,tree[Right].sum);
tree[node].sum=hh; //cout<<"node:"<<node<<" val:"<<tree[node].sum<<" high:"<<tree[node].high<<endl;
}
ll query(ll node,ll l,ll r,ll i,ll j){
if(l>j || r<i){
return 0;
}
if(l>=i && r<=j){//cout<<"node:"<<node<<" val:"<<tree[node].sum<<endl; cout<<"l:"<<l<<" r:"<<r<<endl;
if(tree[node].sum>res){
res=tree[node].sum;
}
return tree[node].high;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
ll p1=query(Left,l,mid,i,j);
ll p2=query(Right,mid+1,r,i,j);
if(p1+p2>res){ //cout<<p1<<"+"<<p2<<endl;
res=p1+p2;
}
return max(p1,p2);
}
void update(ll node,ll l,ll r,ll pos,ll val){
if(l>pos || r<pos){
return;
}
if(l==r){
tree[node].high=val;
tree[node].sum=val;
return;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
update(Left,l,mid,pos,val);
update(Right,mid+1,r,pos,val);
tree[node].high=max(tree[Left].high,tree[Right].high);
tree[node].sum=max(tree[node].sum,tree[Left].high+tree[Right].high);
}
int main(){
ll n,i,j;
while(scanf("%lld",&n)==1){
for(i=1;i<=n;i++){
scanf("%lld",&arr[i]);
}
init(1,1,n);
char ch;
ll q;
scanf("%lld",&q);
getchar();
for(i=1;i<=q;i++){
scanf("%c",&ch);
if(ch=='Q'){
ll x,y; //cout<<"Q pressed"<<endl;
scanf("%lld %lld",&x,&y);
query(1,1,n,x,y);
printf("%lld\n",res);
res=-1;
//state=0;
}
else{
ll x,y;
scanf("%lld %lld",&x,&y);
update(1,1,n,x,y);
}
getchar();
}
}
return 0;
}
i dont know why bt cant see the problem description in that link :(
here is the problem description.
` ~~~~~ You are given a sequence A[1], A[2], ..., A[N] ( 0 ≤ A[i] ≤ 10^8 , 2 ≤ N ≤ 10^5 ). There are two types of operations and they are defined as follows: Update: This will be indicated in the input by a 'U' followed by space and then two integers i and x.
U i x, 1 ≤ i ≤ N, and x, 0 ≤ x ≤ 10^8.
This operation sets the value of A[i] to x.
Query: This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.
Q x y, 1 ≤ x < y ≤ N.
You must find i and j such that x ≤ i, j ≤ y and i != j, such that the sum A[i]+A[j] is maximized. Print the sum A[i]+A[j].
Input
The first line of input consists of an integer N representing the length of the sequence. Next line consists of N space separated integers A[i]. Next line contains an integer Q, Q ≤ 10^5, representing the number of operations. Next Q lines contain the operations.
Output
Output the maximum sum mentioned above, in a separate line, for each Query.
Example
~~~~~
`
Mistake in update method.
pls provide me some i/o for which my code fails.
i would be grateful if u point out what mistake i've done SkyFire
thank u :)
should not the ans be 2??? SkyFire my code gives 2 as a output.
What is your compiler version and options?
http://ideone.com/liPU8O
use pastebin, please