Cod sursa(job #2913266)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 13 iulie 2022 16:21:45
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.5 kb
#include <iostream>
#include <vector>

using namespace std;

#define aintNull {0, 0, 0, 1, 1};
struct aintData {
    int maxSeq;
    int maxl, maxr;
    bool oc;
    int size;
};
#define lazyData int
aintData leaf = {1, 1, 1, 0, 1};

// #DEFINE aintNull 
// #DEFINE aintData 
// #DEFINE lazyData
// #DEFINE leaf
struct AINT {
    int offset;
    int n;
    vector<aintData> aint;
    vector<lazyData> lazy;

    void inheritLazy (int nod)
    {
        if (lazy[nod] == -1)
        {
            int sz = aint[nod].size;
            aint[nod] = {sz, sz, sz, 0, sz};
        }
        else if (lazy[nod] == 1) {
            aint[nod] = {0, 0, 0, 1, aint[nod].size};
        }
        if (nod <= offset){
            lazy[2 * nod] += lazy[nod];
            lazy[2 * nod + 1] += lazy[nod];
            lazy[nod] = 0;
        }
        else {
            aint[nod].oc = (lazy[nod] == 1) ? 1 : 0;
            lazy[nod] = 0;
        }
    }

    aintData merge (int n1, int n2)
    {
        int size = aint[n1].size + aint[n2].size;
        
        int left = aint[n1].maxl;
        if (aint[n1].oc || lazy[n1] == 1) left = 0;
        else if (left == aint[n1].size && !(aint[n2].oc || lazy[n2] == 1)) {
            left += aint[n2].maxl;
        }
        int right = aint[n2].maxr;
        if (aint[n2].oc || lazy[n2]) right = 0;
        else if (right == aint[n2].size && !(aint[n1].oc || lazy[n1] == 1)) {
            right += aint[n1].maxr;
        }
        
        int maxS = max((aint[n1].oc || lazy[n1] == 1) ? 0 : aint[n1].maxSeq,
        (aint[n2].oc || lazy[n2] == 1) ? 0 : aint[n2].maxSeq);
        maxS = max(maxS, ((aint[n1].oc || lazy[n1] == 1) ? 0 :
        aint[n1].maxr) + ((aint[n1].oc || lazy[n1] == 1) ? 0 : aint[n2].maxl));
        maxS = max(maxS, max(left, right));
        
        return {maxS, left, right, aint[n1].oc & aint[n2].oc, size};
    }

    aintData mergeQuery (aintData q1, aintData q2)
    {
        int size = q1.size + q2.size;
        int fre1 = (q1.oc) ? 0 : 1;
        int fre2 = (q2.oc) ? 0 : 1;
        int left = q1.maxl;
        if (q1.oc) left = 0;
        else if (left == q1.size && !q2.oc) {
            left += q2.maxl;
        }
        int right = q2.maxr;
        if (q2.oc)  right = 0;
        else if (right == q2.size && !q1.oc) {
            right += q1.maxr;
        }
        
        int maxS = max((!q1.oc) ? q1.maxSeq : 0,
                        (!q2.oc) ? q2.maxSeq : 0);
        maxS = max(maxS, (!q1.oc) ? q1.maxr : 0 + (!q2.oc) ? q2.maxl : 0);
        maxS = max(maxS, max(left, right));
        
        return {maxS, left, right, q1.oc & q2.oc, size};
    }

    aintData totalVal (int nod)
    {
        if (lazy[nod] == 1 || aint[nod].oc) return {0, 0, 0, 1, 0};
        return aint[nod];
    }

    void build(int nod, int l, int r)
    {
        if (l == r){
            if (l <= n)
            {
                aint[nod] = leaf;
            }
            return;
        }
        int m = (l + r) / 2;
        build (2 * nod, l, m);
        build (2 * nod + 1, m + 1, r);
        aint[nod] = merge(2 * nod, 2 * nod + 1);
    }

    void buildRec ()
    {
        build(1, 1, n);
    }
    
    AINT(int N)
    {
        offset = 1;
        n = N;
        while (offset < N) offset *= 2;
        aint.resize(2 * offset + 1);
        lazy.resize(2 * offset + 1, 0);
        buildRec();
    }

    void upd (int nod, int l, int r, int ul, int ur, long long val)
    {        
        if (ul <= l && r <= ur)
        {
            lazy[nod] += val;
            return;
        }
        if (l > ur || r < ul) return;
        int m = (l + r) / 2;
        inheritLazy(nod);
        upd(2 * nod    , l  , m  , ul, ur, val);
        upd(2 * nod + 1, m + 1, r, ul, ur, val);
        aint[nod] = merge(2 * nod, 2 * nod + 1);
    }

    void lazyUpdate (int l, int r, long long val)
    {
        upd(1, 1, n, l, r, val);
    }
    
    void asn(int nod, int l, int r, int pos, aintData val)
    {
        if (l > pos || r < pos) return;
        if (l == r) {
            aint[nod] = val;
            return;
        }
        int m = (l + r) / 2;
        inheritLazy(nod);
        asn(2 * nod, l, m, pos, val);
        asn(2 * nod + 1, m + 1, r, pos, val);
        aint[nod] = merge(2 * nod, 2 * nod + 1);
    }
 
    void assign (int pos, aintData val)
    {
        asn(1, 1, n, pos, val);
    }

    aintData qry (int nod, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return totalVal(nod);
        }
        if (r < ql || l > qr) return aintNull;
        int m = (l + r) / 2;
        inheritLazy(nod);
        aint[nod] = merge(2 * nod, 2 * nod + 1);

        return mergeQuery(qry (2 * nod, l, m, ql, qr), 
                qry (2 * nod + 1, m + 1, r, ql, qr));
    }

    aintData query(int l, int r)
    {
        return qry(1, 1, n, l, r);
    }

};

int main ()
{
    int n, m; cin >> n >> m;
    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);
    AINT aint(n);
    while (m--)
    {
        int q; cin >> q;
        if (q == 3){
            aintData ans = aint.query(1, n);
            cout << ans.maxSeq << '\n';
        }
        else if (q == 1)
        {
            int s, g; cin >> s >> g;
            aint.lazyUpdate(s, s + g - 1, 1);
        }
        else {
            int s, g; cin >> s >> g;
            aint.lazyUpdate(s, s + g - 1, -1);
        }
    }
}