Pagini recente » Cod sursa (job #1824600) | Cod sursa (job #3134895) | Cod sursa (job #707601) | Cod sursa (job #3220591) | Cod sursa (job #2634906)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("hotel.in");
ofstream out("hotel.out");
int n, queries;
class segTree
{
private:
struct sg
{
int maxOpenLeft, maxOpenRight, maxSequence;
sg() { maxSequence=maxOpenRight=maxOpenLeft=1; }
};
vector <sg> vec;
vector <char> lazy;
void updateRecursion(int poz, int st, int dr, int qst, int qdr, char purpose)
{
/*if(queries==1)
cout<<st<<" "<<dr<<" "<<"\n";*/
int mij=(st+dr)/2;
int leftChild = (st==dr) ? vec.size()-1 : poz + 1;
int rightChild = (st==dr) ? vec.size()-1 : poz + 2*(mij-st+1);
if(lazy[poz]!=0)
{
if(lazy[poz]==1)
vec[poz].maxOpenLeft=vec[poz].maxOpenRight=vec[poz].maxSequence=0;
else if(lazy[poz]==-1)
vec[poz].maxOpenLeft=vec[poz].maxOpenRight=vec[poz].maxSequence=dr-st+1;
lazy[leftChild]=lazy[rightChild]=lazy[poz]; lazy[poz]=0;
}
if(st>qdr||dr<qst) return;
if(qst<=st&&dr<=qdr) ///daca am ajuns sa fac update unui interval intreg, inseamna ca tot intervalul respectiv are o singura valoare
{
lazy[rightChild]=lazy[leftChild]=purpose;
if(purpose==1)
vec[poz].maxOpenLeft=vec[poz].maxOpenRight=vec[poz].maxSequence=0;
else
vec[poz].maxOpenLeft=vec[poz].maxOpenRight=vec[poz].maxSequence=dr-st+1;
return;
}
updateRecursion(leftChild, st, mij, qst, qdr, purpose);
updateRecursion(rightChild, mij+1, dr, qst, qdr, purpose);
sg & x=vec[leftChild], & y=vec[rightChild];
vec[poz].maxSequence=max({x.maxOpenRight+y.maxOpenLeft, x.maxSequence, y.maxSequence});
vec[poz].maxOpenLeft=(x.maxOpenLeft==mij-st+1) ? x.maxOpenLeft+y.maxOpenLeft : x.maxOpenLeft;
vec[poz].maxOpenRight=(y.maxOpenRight==dr-(mij+1)+1) ? y.maxOpenRight+x.maxOpenRight : y.maxOpenRight;
}
void build(int poz, int st, int dr)
{
int mij=(st+dr)/2;
int leftChild = (st==dr) ? vec.size()-1 : poz + 1;
int rightChild = (st==dr) ? vec.size()-1 : poz + 2*(mij-st+1);
if(st==dr)
return;
build(leftChild, st, mij); build(rightChild, mij+1, dr);
vec[poz].maxOpenRight=vec[poz].maxOpenLeft=vec[poz].maxSequence=dr-st+1;
}
public:
segTree (int n)
{
vec.resize(2*n+1);
vec.shrink_to_fit();
lazy.resize(2*n+1, 0);
lazy.shrink_to_fit();
build(1, 1, n);
}
void update(int st, int dr, char purpose)
{
updateRecursion(1, 1, n, st, dr, purpose);
}
int getMax()
{
return vec[1].maxSequence;
}
};
int caz, x, y;
int main()
{
in>>n>>queries;
segTree tree(n);
while(queries--)
{
in>>caz;
if(caz==1)
{
in>>x>>y;
tree.update(x, x+y-1, +1);
}
if(caz==2)
{
in>>x>>y;
tree.update(x, x+y-1, -1);
}
if(caz==3)
out<<tree.getMax()<<"\n";
}
return 0;
}