Mai intai trebuie sa te autentifici.
Cod sursa(job #2956854)
Utilizator | 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;
}