Cod sursa(job #1350339)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 20 februarie 2015 19:24:06
Problema A+B Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<cstdio>
const int N=100000;
class Node{
    public:
        int smax,l,r,s;
        Node(int a){
            smax=a;
            l=a;
            r=a;
            s=a;
        }
        Node(){
        }
};
int v[N+1];
Node arbint[4*N+1];
int k,n,p,val;
Node f1,f2;
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
int max3(int a,int b,int c){
    return max2(a,max2(b,c));
}
void build(int st,int dr,int pos){
    if(st==dr){
        k++;
        arbint[pos]=Node(v[k]);
        return;
    }
    int m=(st+dr)/2;
    build(st,m,pos*2);
    build(m+1,dr,pos*2+1);
    f1=arbint[pos*2];
    f2=arbint[pos*2+1];
    arbint[pos].smax=max3(f1.smax,f2.smax,f1.r+f2.l);
    arbint[pos].s=f1.s+f2.s;
    arbint[pos].l=max3(f1.l,f1.s,f1.s+f2.l);
    arbint[pos].r=max3(f2.r,f2.s,f2.s+f1.r);
}
void update(int st,int dr,int pos){
    if(st==dr){
        arbint[pos]=Node(val);
        return;
    }
    int m=(st+dr)/2;
    if(p<=m)
        update(st,m,pos*2);
    else
        update(m+1,dr,pos*2+1);
    f1=arbint[pos*2];
    f2=arbint[pos*2+1];
    arbint[pos].smax=max3(f1.smax,f2.smax,f1.r+f2.l);
    arbint[pos].s=f1.s+f2.s;
    arbint[pos].l=max3(f1.l,f1.s,f1.s+f2.l);
    arbint[pos].r=max3(f2.r,f2.s,f2.s+f1.r);
}
int main(){
    int q;
    freopen("adunare.in","r",stdin);
    freopen("adunare.out","w",stdout);
    scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        v[i]=1;
    for(int i=1;i<=4*n;i++)
        arbint[i].l=arbint[i].r=arbint[i].s=arbint[i].smax=1;
    printf("%d",n+q);
    /*for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    build(1,n,1);
    if(arbint[1].smax>0)
        printf("%d\n",arbint[1].smax);
    else
        printf("0\n");
    while(q){
        q--;
        scanf("%d%d",&p,&val);
        update(1,n,1);
        if(arbint[1].smax>0)
            printf("%d\n",arbint[1].smax);
        else
            printf("0\n");
    }*/

    return 0;
}