Cod sursa(job #2634906)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 12 iulie 2020 17:47:18
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.22 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(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;
}