oj.uz

Submission #335485

# Submission time Handle Problem Language Result Execution time Memory
335485 2020-12-12T18:43:42 Z mihai145 Progression (NOI20_progression) C++14
9 / 100
 1195 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 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
            {
                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 547 ms 86764 KB Output is correct
2 Correct 249 ms 85356 KB Output is correct
3 Correct 236 ms 85356 KB Output is correct
4 Correct 234 ms 85228 KB Output is correct
5 Correct 237 ms 85228 KB Output is correct
6 Correct 237 ms 85228 KB Output is correct
7 Correct 240 ms 85228 KB Output is correct
8 Correct 51 ms 84972 KB Output is correct
9 Correct 52 ms 84844 KB Output is correct
10 Correct 53 ms 84844 KB Output is correct
11 Correct 554 ms 86764 KB Output is correct
12 Correct 555 ms 86636 KB Output is correct
13 Correct 546 ms 87020 KB Output is correct
14 Correct 551 ms 86892 KB Output is correct
15 Correct 545 ms 86892 KB Output is correct
16 Correct 555 ms 86764 KB Output is correct
17 Correct 549 ms 86668 KB Output is correct
18 Correct 551 ms 86636 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 Correct 54 ms 84844 KB Output is correct
3 Incorrect 52 ms 84844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 529 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 1195 ms 86380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 529 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 547 ms 86764 KB Output is correct
2 Correct 249 ms 85356 KB Output is correct
3 Correct 236 ms 85356 KB Output is correct
4 Correct 234 ms 85228 KB Output is correct
5 Correct 237 ms 85228 KB Output is correct
6 Correct 237 ms 85228 KB Output is correct
7 Correct 240 ms 85228 KB Output is correct
8 Correct 51 ms 84972 KB Output is correct
9 Correct 52 ms 84844 KB Output is correct
10 Correct 53 ms 84844 KB Output is correct
11 Correct 554 ms 86764 KB Output is correct
12 Correct 555 ms 86636 KB Output is correct
13 Correct 546 ms 87020 KB Output is correct
14 Correct 551 ms 86892 KB Output is correct
15 Correct 545 ms 86892 KB Output is correct
16 Correct 555 ms 86764 KB Output is correct
17 Correct 549 ms 86668 KB Output is correct
18 Correct 551 ms 86636 KB Output is correct
19 Correct 55 ms 84844 KB Output is correct
20 Correct 54 ms 84844 KB Output is correct
21 Incorrect 52 ms 84844 KB Output isn't correct
22 Halted 0 ms 0 KB -