Cod sursa(job #1738296)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 6 august 2016 13:37:57
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <cstdio>
#include <algorithm>
#define MAX 65536
#define MaxN 1700001
using namespace std;
  
int p=0,N,P,V1,V2,Type,sign,X;
char f[MAX];
int MX(int a,int b,int c)
{
    X=max(a,b);
    X=max(X,c);
    return X;
}
struct Tree
{
    int R,L,Start,End,All;
}v[MaxN];
void r(int &nr)
{
    nr=0;
    sign=0;
    while(f[p]<'0'||f[p]>'9')
    {
        if(f[p]=='-')
            sign=1;
        p++;
        if(p==MAX)
            fread(f,1,MAX,stdin),p=0;
     }
    while(f[p]>='0'&&f[p]<='9')
    {
        nr=nr*10+f[p++]-'0';
        if(p==MAX)
            fread(f,1,MAX,stdin),p=0;
    }
    if(sign==1)
        nr=-nr;
}
void CreateNode(int pos,int L,int R)
{
    v[pos].L=L;v[pos].R=R;
    v[pos].Start=R-L+1;
    v[pos].End=R-L+1;
    v[pos].All=R-L+1;
    if(L<R)
    {
        int mid=(L+R)>>1;
        CreateNode(2*pos,L,mid);
        CreateNode(2*pos+1,mid+1,R);
    }
}
void Answer()
{
    printf("%d\n",v[1].All);
}
void Add(int A,int B,int pos,int mid)
{
    if(v[pos].L>=A&&v[pos].R<=B)
        v[pos].All=v[pos].End=v[pos].Start=0;
    if(v[pos].L<v[pos].R)
        mid=(v[pos].R+v[pos].L)>>1;
    else return;
    if(mid>=A)
        Add(A,B,2*pos,1);
    if(mid<B)
        Add(A,B,2*pos+1,1);
    v[pos].All=MX(v[pos*2].All,v[2*pos+1].All,v[pos*2].End+v[pos*2+1].Start);
    v[pos].Start=v[pos*2].Start+(v[pos*2].Start==v[2*pos].R-v[2*pos].L+1)*v[pos*2+1].Start;
    v[pos].End=v[pos*2+1].End+(v[pos*2+1].End==v[2*pos+1].R-v[2*pos+1].L+1)*v[pos*2].End;
}
void Remove(int A,int B,int pos,int mid)
{
    if(v[pos].L>=A&&v[pos].R<=B)
        v[pos].All=v[pos].End=v[pos].Start=v[pos].R-v[pos].L+1;
    if(v[pos].L<v[pos].R)
        mid=(v[pos].R+v[pos].L)>>1;
    else return;
    if(mid>=A)
        Remove(A,B,2*pos,1);
    if(mid<B)
        Remove(A,B,2*pos+1,1);
    v[pos].All=MX(v[pos*2].All,v[2*pos+1].All,v[pos*2].End+v[pos*2+1].Start);
    v[pos].Start=v[pos*2].Start+(v[pos*2].Start==v[2*pos].R-v[2*pos].L+1)*v[pos*2+1].Start;
    v[pos].End=v[pos*2+1].End+(v[pos*2+1].End==v[2*pos+1].R-v[2*pos+1].L+1)*v[pos*2].End;
}
int main()
{
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    fread(f,1,MAX,stdin);
    r(N);r(P);
    CreateNode(1,1,N);
    for(int i=1;i<=P;i++)
    {
        r(Type);
        if(Type==3)
            Answer();
        else if(Type==1)
        {
            r(V1);r(V2);
            Add(V1,V1+V2-1,1,1);
        }
        else if(Type==2)
        {
            r(V1);r(V2);
            Remove(V1,V1+V2-1,1,1);
        }
    }
    return 0;
}