Submission #335487

#	Time	Username	Problem	Language	Result	Execution time	Memory
335487		mihai145	Progression (NOI20_progression)	C++14	100 / 100	2290 ms	96748 KiB

Progression

#include <iostream>

using namespace std;

const int NMAX = 3e5;
int N, Q, d[NMAX + 2];

struct Node
{

    bool dummy;

    long long sum;

    int sz;

    int maxPref;
    long long valPref;
    int maxSuf;
    long long valSuf;
    int maxProgression;

    bool lfinc, rginc;

    int lazyType;
    long long lazyVal;

    Node()
    {
        dummy = false;

        sum = 0LL;
        sz = 0LL;

        maxPref = 0;
        valPref = 0LL;
        maxSuf = 0;
        valSuf = 0LL;

        maxProgression = 0;

        lfinc = rginc = false;

        lazyType = 0;
        lazyVal = 0LL;
    }
};

Node Merge(Node A, Node B)
{

    if(A.dummy == true)
        return B;

    if(B.dummy == true)
        return A;

    Node R;

    R.sz = A.sz + B.sz;
    R.sum = A.sum + B.sum;

    if(A.maxPref == A.sz)
    {
        if(A.valPref == B.valPref)
        {
            R.maxPref = A.sz + B.maxPref;
            R.valPref = A.valPref;
        }
        else
        {
            R.maxPref = A.sz;
            R.valPref = A.valPref;
        }
    }
    else
    {
        R.maxPref = A.maxPref;
        R.valPref = A.valPref;
    }

    if(B.maxSuf == B.sz)
    {
        if(B.valSuf == A.valSuf)
        {
            R.maxSuf = B.sz + A.maxSuf;
            R.valSuf = B.valSuf;
        }
        else
        {
            R.maxSuf = B.sz;
            R.valSuf = B.valSuf;
        }
    }
    else
    {
        R.maxSuf = B.maxSuf;
        R.valSuf = B.valSuf;
    }

    R.maxProgression = R.maxPref;
    R.lfinc = true;

    if(R.maxSuf >= R.maxProgression)
    {
        R.maxProgression = R.maxSuf;
        R.lfinc = false;
        R.rginc = true;
    }

    if(A.maxProgression > R.maxProgression)
    {
        R.maxProgression = A.maxProgression;
        R.lfinc = false, R.rginc = false;

        if(A.lfinc == true) R.lfinc = true;
    }

    if(B.maxProgression >= R.maxProgression)
    {
        R.maxProgression = B.maxProgression;
        R.lfinc = false, R.rginc = false;

        if(B.rginc == true) R.rginc = true;
    }

    if(A.valSuf == B.valPref)
    {
        if(A.maxSuf + B.maxPref > R.maxProgression)
        {
            R.maxProgression = A.maxSuf + B.maxPref;
            R.lfinc = false;
            R.rginc = false;
        }
    }

    if(R.maxProgression == R.sz)
    {
        R.lfinc = true;
        R.rginc = true;
    }

    return R;
}

struct SegTree
{

    Node v[4 * NMAX];

    void Build(int node, int st, int dr)
    {
        if(st == dr)
        {
            v[node].sz = dr - st + 1;
            v[node].sum = v[node].valPref = v[node].valSuf = d[st] - d[st - 1];
            v[node].maxPref = v[node].maxSuf = v[node].maxProgression = 1;

            v[node].lfinc = v[node].rginc = false;

            return ;
        }

        int mid = (st + dr) >> 1;

        Build(2 * node, st, mid);
        Build(2 * node + 1, mid + 1, dr);

        v[node] = Merge(v[2 * node], v[2 * node + 1]);
    }

    /*
    void AddPoint(int node, int st, int dr, int pos, long long val) {

    }
    */

    /*
    void SetPoint(int node, int st, int dr, int pos, long long val) {

    }
    */

    void Propagate(int node, int st, int dr)
    {
        if(v[node].lazyType == 0)
            return ;

        int szNode = dr - st + 1;

        if(v[node].lazyType == 1)
        {

            v[node].sum += v[node].lazyVal * szNode;
            v[node].valPref += v[node].lazyVal;
            v[node].valSuf += v[node].lazyVal;

            if(szNode > 1)
            {

                int mid = (st + dr) >> 1;

                if(v[2 * node].lazyType == 2)
                {
                    Propagate(2 * node, st, mid);
                }

                v[2 * node].lazyType = 1;
                v[2 * node].lazyVal += v[node].lazyVal;

                if(v[2 * node + 1].lazyType == 2)
                {
                    Propagate(2 * node + 1, mid + 1, dr);
                }

                v[2 * node + 1].lazyType = 1;
                v[2 * node + 1].lazyVal += v[node].lazyVal;
            }

        }
        else
        {

            v[node].sum = v[node].lazyVal * szNode;
            v[node].valPref = v[node].valSuf = v[node].lazyVal;
            v[node].maxPref = v[node].maxSuf = v[node].maxProgression = szNode;

            v[node].lfinc = true;
            v[node].rginc = true;

            if(szNode > 1)
            {
                v[2 * node].lazyType = 2;
                v[2 * node].lazyVal = v[node].lazyVal;

                v[2 * node + 1].lazyType = 2;
                v[2 * node + 1].lazyVal = v[node].lazyVal;
            }

        }

        v[node].lazyType = 0;
        v[node].lazyVal = 0;
    }

    void AddRange(int node, int st, int dr, int l, int r, long long val)
    {
        Propagate(node, st, dr);

        if(r < st || l > dr)
            return ;

        if(l <= st && dr <= r)
        {
            v[node].lazyType = 1;
            v[node].lazyVal = val;
            Propagate(node, st, dr);

            return ;
        }

        int mid = (st + dr) >> 1;

        AddRange(2 * node, st, mid, l, r, val);
        AddRange(2 * node + 1, mid + 1, dr, l, r, val);

        v[node] = Merge(v[2 * node], v[2 * node + 1]);
    }

    void SetRange(int node, int st, int dr, int l, int r, long long val)
    {
        Propagate(node, st, dr);

        if(r < st || l > dr)
            return ;

        if(l <= st && dr <= r)
        {
            v[node].lazyType = 2;
            v[node].lazyVal = val;
            Propagate(node, st, dr);

            return ;
        }

        int mid = (st + dr) >> 1;

        SetRange(2 * node, st, mid, l, r, val);
        SetRange(2 * node + 1, mid + 1, dr, l, r, val);

        v[node] = Merge(v[2 * node], v[2 * node + 1]);
    }

    Node Query(int node, int st, int dr, int l, int r)
    {
        Propagate(node, st, dr);

        if(r < st || l > dr)
        {
            Node _dummy;
            _dummy.dummy = true;
            return _dummy;
        }

        if(l <= st && dr <= r)
            return v[node];

        int mid = (st + dr) >> 1;

        Node a1 = Query(2 * node, st, mid, l, r);
        Node a2 = Query(2 * node + 1, mid + 1, dr, l, r);

        return Merge(a1, a2);
    }

};

SegTree aint;

int main()
{
    // The following line disables syncing between cin/scanf and cout/printf.
    // It makes input faster, but you must not use functions from <cstdio> (e.g. scanf/printf) directly.
    // This line must be executed before any use of cin/cout.
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // Your code goes here ...
    // (You can now read input and write output normally using cin/cout.)

    cin >> N >> Q;

    for(int i = 1; i <= N; i++)
        cin >> d[i];

    aint.Build(1, 1, N);

    /*
    cout << "------------------------\n";
        for(int j = 1; j <= N; j++)
            cout << aint.Query(1, 1, N, j, j).sum << ' ';
    cout << '\n';
    cout << "------------------------\n";
    */

    for(int i = 1; i <= Q; i++)
    {
        int typ;
        cin >> typ;

        if(typ == 1)
        {
            ///patch

            int L, R, S, C;
            cin >> L >> R >> S >> C;

            long long rr = 0;
            if(R + 1 <= N)
            {
                rr = aint.Query(1, 1, N, 1, R + 1).sum;
            }

            if(L + 1 <= R)
                aint.AddRange(1, 1, N, L + 1, R, C);

            aint.AddRange(1, 1, N, L, L, S);

            if(R + 1 <= N)
                aint.SetRange(1, 1, N, R + 1, R + 1, rr - aint.Query(1, 1, N, 1, R).sum);
        }
        else if(typ == 2)
        {
            ///rewrite

            int L, R, S, C;
            cin >> L >> R >> S >> C;

            long long rr = 0;
            if(R + 1 <= N)
            {
                rr = aint.Query(1, 1, N, 1, R + 1).sum;
            }

            long long l = 0;
            if(L - 1 >= 1) l = aint.Query(1, 1, N, 1, L - 1).sum;
            aint.SetRange(1, 1, N, L, L, S - l);

            if(L + 1 <= R)
                aint.SetRange(1, 1, N, L + 1, R, C);

            if(R + 1 <= N)
            {
                aint.SetRange(1, 1, N, R + 1, R + 1, rr - aint.Query(1, 1, N, 1, R).sum);
            }
        }
        else
        {
            ///evaluate

            int L, R;
            cin >> L >> R;

            if(L == R)
                cout << 1 << '\n';
            else
            {
                cout << aint.Query(1, 1, N, L + 1, R).maxProgression + 1 << '\n';

                /*
                if(res.maxProgression != res.sz)
                {
                    if(!res.lfinc)
                        cout << 1 + res.maxProgression << '\n';
                    else
                        cout << res.maxProgression << '\n';
                }
                else
                    cout << res.maxProgression << '\n';
                */
            }
        }

        /*
        cout << "------------------------\n";
        for(int j = 1; j <= N; j++)
            cout << aint.Query(1, 1, N, j, j).sum << ' ';
        cout << '\n';
        cout << "------------------------\n";
        */
    }

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17