Cod sursa(job #2956854)

Utilizator Luca529Taschina Luca Luca529 Data 20 decembrie 2022 20:56:23
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
struct Data{
int a, pref, suf, v, p;
}x[400001];

Data C(Data a, Data b, int st, int dr)
{Data c;
 int mij=(st+dr)/2;
 if(a.p==0)c.pref=b.pref+mij-st+1;
 else c.pref=a.pref;

 if(b.p==0)c.suf=dr-mij+a.suf;
 else c.suf=b.suf;

 c.p=max(a.p, b.p);
 c.v=max(a.suf+b.pref, max(a.v, b.v));
 c.a=0;
 return c;
}

void Build(int nod, int st, int dr)
{if(st==dr)
 x[nod].suf=x[nod].pref=x[nod].v=1, x[nod].p=x[nod].a=0;
 else
 {int mij=(st+dr)/2;
  Build(nod*2, st, mij);
  Build(nod*2+1, mij+1, dr);

  x[nod]=C(x[nod*2], x[nod*2+1], st, dr);
 }
}

void La(int nod, int st, int dr)
{if(st!=dr)
 {x[nod*2].a+=x[nod].a;
  x[nod*2+1].a+=x[nod].a;
 }
 if(x[nod].a==1)
 {x[nod].p=1;
  x[nod].suf=x[nod].pref=x[nod].v=0;
 }
 else
 {x[nod].p=0;
  x[nod].suf=x[nod].pref=x[nod].v=dr-st+1;
 }
 x[nod].a=0;
}

void Update(int nod, int st, int dr, int us, int ud, int val)
{if(x[nod].a!=0)La(nod, st, dr);
 if(us<=st && dr<=ud)
 {x[nod].a+=val;
  La(nod, st, dr);
 }
 else
 {int mij=(st+dr)/2;

  if(mij>=us)Update(nod*2, st, mij, us, ud, val);
  if(mij<ud)Update(nod*2+1, mij+1, dr, us, ud, val);

  if(x[nod*2+1].a!=0)La(nod*2+1, mij+1, dr);
  if(x[nod*2].a!=0)La(nod*2, st, mij);
  x[nod]=C(x[nod*2], x[nod*2+1], st, dr);
 }
}

int main()
{   int n, m, t, a, b;
    fin>>n>>m;
    Build(1, 1, n);

    for(int i=1;i<=m;i++)
    {fin>>t;
     if(t==1)
     {fin>>a>>b;
      Update(1, 1, n, a, a+b-1, 1);
     }
     else if(t==2)
     {fin>>a>>b;
      Update(1, 1, n, a, a+b-1, -1);
     }
     else fout<<x[1].v<<"\n";
     /*
     for(int i=1;i<=n*3;i++)cout<<x[i].a<<" ";
     cout<<endl;
     */
    }
    return 0;
}