oj.uz

Submission #335477

# Submission time Handle Problem Language Result Execution time Memory
335477 2020-12-12T18:15:53 Z mihai145 Progression (NOI20_progression) C++14
9 / 100
 1092 ms 87148 KB 
#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;

            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 567 ms 86764 KB Output is correct
2 Correct 250 ms 85256 KB Output is correct
3 Correct 238 ms 85228 KB Output is correct
4 Correct 244 ms 85228 KB Output is correct
5 Correct 237 ms 85272 KB Output is correct
6 Correct 239 ms 85228 KB Output is correct
7 Correct 241 ms 85228 KB Output is correct
8 Correct 52 ms 84844 KB Output is correct
9 Correct 53 ms 84844 KB Output is correct
10 Correct 52 ms 84844 KB Output is correct
11 Correct 562 ms 86964 KB Output is correct
12 Correct 582 ms 86672 KB Output is correct
13 Correct 549 ms 86892 KB Output is correct
14 Correct 554 ms 87020 KB Output is correct
15 Correct 557 ms 87020 KB Output is correct
16 Correct 554 ms 86636 KB Output is correct
17 Correct 565 ms 86636 KB Output is correct
18 Correct 558 ms 86892 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 84844 KB Output is correct
2 Incorrect 53 ms 84844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 86764 KB Output is correct
2 Correct 250 ms 85256 KB Output is correct
3 Correct 238 ms 85228 KB Output is correct
4 Correct 244 ms 85228 KB Output is correct
5 Correct 237 ms 85272 KB Output is correct
6 Correct 239 ms 85228 KB Output is correct
7 Correct 241 ms 85228 KB Output is correct
8 Correct 52 ms 84844 KB Output is correct
9 Correct 53 ms 84844 KB Output is correct
10 Correct 52 ms 84844 KB Output is correct
11 Correct 562 ms 86964 KB Output is correct
12 Correct 582 ms 86672 KB Output is correct
13 Correct 549 ms 86892 KB Output is correct
14 Correct 554 ms 87020 KB Output is correct
15 Correct 557 ms 87020 KB Output is correct
16 Correct 554 ms 86636 KB Output is correct
17 Correct 565 ms 86636 KB Output is correct
18 Correct 558 ms 86892 KB Output is correct
19 Correct 55 ms 84844 KB Output is correct
20 Incorrect 53 ms 84844 KB Output isn't correct
21 Halted 0 ms 0 KB -