oj.uz

Submission #335475

# Submission time Handle Problem Language Result Execution time Memory
335475 2020-12-12T18:14:39 Z mihai145 Progression (NOI20_progression) C++14
9 / 100
 1170 ms 222036 KB 
#include <iostream>

using namespace std;

const int NMAX = 1e6;
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[3 * 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;

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

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

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

        }
        else if(typ == 2)
        {
            ///rewrite

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

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

            if(R + 1 <= N)
            {
                Node rr = aint.Query(1, 1, N, 1, R + 1);
                aint.SetRange(1, 1, N, R + 1, R + 1, rr.sum - S - 1LL * (R - L) * C);
            }

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

        }
        else
        {
            ///evaluate

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

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

                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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 219372 KB Output is correct
2 Correct 316 ms 215020 KB Output is correct
3 Correct 317 ms 215004 KB Output is correct
4 Correct 316 ms 214892 KB Output is correct
5 Correct 315 ms 215020 KB Output is correct
6 Correct 315 ms 215276 KB Output is correct
7 Correct 314 ms 215020 KB Output is correct
8 Correct 129 ms 211820 KB Output is correct
9 Correct 128 ms 211692 KB Output is correct
10 Correct 129 ms 211692 KB Output is correct
11 Correct 633 ms 221548 KB Output is correct
12 Correct 638 ms 221548 KB Output is correct
13 Correct 640 ms 222036 KB Output is correct
14 Correct 629 ms 221932 KB Output is correct
15 Correct 625 ms 221676 KB Output is correct
16 Correct 631 ms 221548 KB Output is correct
17 Correct 633 ms 221676 KB Output is correct
18 Correct 634 ms 221676 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 211832 KB Output is correct
2 Incorrect 127 ms 211692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 605 ms 217708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1170 ms 220524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 605 ms 217708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 219372 KB Output is correct
2 Correct 316 ms 215020 KB Output is correct
3 Correct 317 ms 215004 KB Output is correct
4 Correct 316 ms 214892 KB Output is correct
5 Correct 315 ms 215020 KB Output is correct
6 Correct 315 ms 215276 KB Output is correct
7 Correct 314 ms 215020 KB Output is correct
8 Correct 129 ms 211820 KB Output is correct
9 Correct 128 ms 211692 KB Output is correct
10 Correct 129 ms 211692 KB Output is correct
11 Correct 633 ms 221548 KB Output is correct
12 Correct 638 ms 221548 KB Output is correct
13 Correct 640 ms 222036 KB Output is correct
14 Correct 629 ms 221932 KB Output is correct
15 Correct 625 ms 221676 KB Output is correct
16 Correct 631 ms 221548 KB Output is correct
17 Correct 633 ms 221676 KB Output is correct
18 Correct 634 ms 221676 KB Output is correct
19 Correct 128 ms 211832 KB Output is correct
20 Incorrect 127 ms 211692 KB Output isn't correct
21 Halted 0 ms 0 KB -