Cod sursa(job #2634701)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 12 iulie 2020 01:10:57
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.17 kb
#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(st==dr)
        {
            lazy[poz]+=purpose;
            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=1;
            lazy[poz]=0;
            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[poz]+=purpose; lazy[rightChild]+=lazy[poz]; lazy[leftChild]+=lazy[poz];

            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[poz]=0;
            return;
        }
        if(lazy[poz]!=0&&!(qst<=mij&&qdr>mij))
        {
            lazy[leftChild]+=lazy[poz]; lazy[rightChild]+=lazy[poz];


            if(qst<=mij)
            {
                updateRecursion(leftChild, st, mij, qst, qdr, purpose); ///analizez stanga
                if(lazy[poz]==1)
                {
                    vec[poz].maxSequence=vec[leftChild].maxSequence;

                    vec[poz].maxOpenLeft=vec[leftChild].maxOpenLeft;

                    vec[poz].maxOpenRight=0;
                }
                else
                {
                    vec[poz].maxSequence=max(vec[leftChild].maxSequence, vec[leftChild].maxOpenRight+dr-(mij+1)+1);

                    vec[poz].maxOpenLeft=(vec[leftChild].maxOpenLeft==mij-st+1) ? dr-st+1 : vec[leftChild].maxOpenLeft;

                    vec[poz].maxOpenRight=vec[leftChild].maxOpenRight+dr-(mij+1)+1;
                }
            }
            else if(qdr>mij)
            {
                updateRecursion(rightChild, mij+1, dr, qst, qdr, purpose); ///analizez dreapta
                if(lazy[poz]==1)
                {
                    vec[poz].maxSequence=vec[rightChild].maxSequence;

                    vec[poz].maxOpenLeft=0;

                    vec[poz].maxOpenRight=vec[rightChild].maxOpenRight;
                }
                else
                {
                    vec[poz].maxSequence=max(vec[rightChild].maxSequence, vec[rightChild].maxOpenLeft+mij-st+1);

                    vec[poz].maxOpenLeft=mij-st+1+vec[rightChild].maxOpenLeft;

                    vec[poz].maxOpenRight=(vec[rightChild].maxOpenRight==dr-(mij+1)+1) ? dr-st+1 : vec[rightChild].maxOpenRight;
                }
            }
            lazy[poz]=0;

            return;
        }

        if(qst<=mij)
            updateRecursion(leftChild, st, mij, qst, qdr, purpose);

        if(qdr>mij)
            updateRecursion(rightChild, mij+1, dr, qst, qdr, purpose);

        vec[poz].maxSequence=max({vec[leftChild].maxOpenRight+vec[rightChild].maxOpenLeft, vec[leftChild].maxSequence, vec[rightChild].maxSequence});

        vec[poz].maxOpenLeft=(vec[leftChild].maxOpenLeft==mij-st+1) ? vec[leftChild].maxOpenLeft+vec[rightChild].maxOpenLeft : vec[leftChild].maxOpenLeft;

        vec[poz].maxOpenRight=(vec[rightChild].maxOpenRight==dr-(mij+1)+1) ? vec[rightChild].maxOpenRight+vec[leftChild].maxOpenRight : vec[rightChild].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;
}