oj.uz

Submission #335487

# Submission time Handle Problem Language Result Execution time Memory
335487 2020-12-12T18:50:22 Z mihai145 Progression (NOI20_progression) C++14
100 / 100
 2290 ms 96748 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;

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

# Verdict Execution time Memory Grader output
1 Correct 666 ms 86764 KB Output is correct
2 Correct 264 ms 85228 KB Output is correct
3 Correct 263 ms 85228 KB Output is correct
4 Correct 262 ms 85212 KB Output is correct
5 Correct 265 ms 85228 KB Output is correct
6 Correct 268 ms 85228 KB Output is correct
7 Correct 264 ms 85228 KB Output is correct
8 Correct 57 ms 84844 KB Output is correct
9 Correct 52 ms 84844 KB Output is correct
10 Correct 54 ms 84972 KB Output is correct
11 Correct 650 ms 86764 KB Output is correct
12 Correct 654 ms 86652 KB Output is correct
13 Correct 654 ms 86892 KB Output is correct
14 Correct 647 ms 86892 KB Output is correct
15 Correct 647 ms 87276 KB Output is correct
16 Correct 705 ms 86752 KB Output is correct
17 Correct 666 ms 86712 KB Output is correct
18 Correct 651 ms 86764 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 84860 KB Output is correct
2 Correct 52 ms 84844 KB Output is correct
3 Correct 62 ms 84844 KB Output is correct
4 Correct 54 ms 84844 KB Output is correct
5 Correct 51 ms 84844 KB Output is correct
6 Correct 52 ms 84844 KB Output is correct
7 Correct 53 ms 84972 KB Output is correct
8 Correct 55 ms 84844 KB Output is correct
9 Correct 56 ms 84844 KB Output is correct
10 Correct 65 ms 84844 KB Output is correct
11 Correct 53 ms 84852 KB Output is correct
12 Correct 55 ms 84972 KB Output is correct
13 Correct 55 ms 84844 KB Output is correct
14 Correct 54 ms 84844 KB Output is correct
15 Correct 57 ms 84972 KB Output is correct
16 Correct 56 ms 84972 KB Output is correct
17 Correct 55 ms 84972 KB Output is correct
18 Correct 56 ms 84972 KB Output is correct
19 Correct 55 ms 84844 KB Output is correct
20 Correct 61 ms 84844 KB Output is correct
21 Correct 53 ms 84844 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 87276 KB Output is correct
2 Correct 193 ms 87660 KB Output is correct
3 Correct 189 ms 87724 KB Output is correct
4 Correct 171 ms 87532 KB Output is correct
5 Correct 203 ms 87788 KB Output is correct
6 Correct 209 ms 87788 KB Output is correct
7 Correct 210 ms 87788 KB Output is correct
8 Correct 51 ms 84844 KB Output is correct
9 Correct 54 ms 84844 KB Output is correct
10 Correct 54 ms 84948 KB Output is correct
11 Correct 652 ms 91756 KB Output is correct
12 Correct 579 ms 93240 KB Output is correct
13 Correct 695 ms 91796 KB Output is correct
14 Correct 664 ms 91784 KB Output is correct
15 Correct 588 ms 93288 KB Output is correct
16 Correct 638 ms 93804 KB Output is correct
17 Correct 624 ms 93676 KB Output is correct
18 Correct 633 ms 93804 KB Output is correct
19 Correct 560 ms 93140 KB Output is correct
20 Correct 549 ms 93236 KB Output is correct
21 Correct 560 ms 93168 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1380 ms 86412 KB Output is correct
2 Correct 334 ms 88556 KB Output is correct
3 Correct 339 ms 88300 KB Output is correct
4 Correct 340 ms 88300 KB Output is correct
5 Correct 351 ms 88300 KB Output is correct
6 Correct 348 ms 88428 KB Output is correct
7 Correct 350 ms 88300 KB Output is correct
8 Correct 51 ms 84844 KB Output is correct
9 Correct 55 ms 84972 KB Output is correct
10 Correct 51 ms 84844 KB Output is correct
11 Correct 1383 ms 92912 KB Output is correct
12 Correct 1397 ms 95992 KB Output is correct
13 Correct 1388 ms 92852 KB Output is correct
14 Correct 1430 ms 92860 KB Output is correct
15 Correct 1393 ms 95852 KB Output is correct
16 Correct 1416 ms 96268 KB Output is correct
17 Correct 1408 ms 96236 KB Output is correct
18 Correct 1408 ms 96260 KB Output is correct
19 Correct 1357 ms 95980 KB Output is correct
20 Correct 1342 ms 96108 KB Output is correct
21 Correct 1349 ms 96108 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 87276 KB Output is correct
2 Correct 193 ms 87660 KB Output is correct
3 Correct 189 ms 87724 KB Output is correct
4 Correct 171 ms 87532 KB Output is correct
5 Correct 203 ms 87788 KB Output is correct
6 Correct 209 ms 87788 KB Output is correct
7 Correct 210 ms 87788 KB Output is correct
8 Correct 51 ms 84844 KB Output is correct
9 Correct 54 ms 84844 KB Output is correct
10 Correct 54 ms 84948 KB Output is correct
11 Correct 652 ms 91756 KB Output is correct
12 Correct 579 ms 93240 KB Output is correct
13 Correct 695 ms 91796 KB Output is correct
14 Correct 664 ms 91784 KB Output is correct
15 Correct 588 ms 93288 KB Output is correct
16 Correct 638 ms 93804 KB Output is correct
17 Correct 624 ms 93676 KB Output is correct
18 Correct 633 ms 93804 KB Output is correct
19 Correct 560 ms 93140 KB Output is correct
20 Correct 549 ms 93236 KB Output is correct
21 Correct 560 ms 93168 KB Output is correct
22 Correct 1735 ms 95800 KB Output is correct
23 Correct 324 ms 88172 KB Output is correct
24 Correct 317 ms 88172 KB Output is correct
25 Correct 319 ms 88172 KB Output is correct
26 Correct 330 ms 88172 KB Output is correct
27 Correct 328 ms 88428 KB Output is correct
28 Correct 331 ms 88300 KB Output is correct
29 Correct 49 ms 84844 KB Output is correct
30 Correct 49 ms 84844 KB Output is correct
31 Correct 48 ms 84972 KB Output is correct
32 Correct 1768 ms 92804 KB Output is correct
33 Correct 1659 ms 95468 KB Output is correct
34 Correct 1752 ms 92908 KB Output is correct
35 Correct 1747 ms 92780 KB Output is correct
36 Correct 1319 ms 92652 KB Output is correct
37 Correct 1315 ms 92788 KB Output is correct
38 Correct 1318 ms 92780 KB Output is correct
39 Correct 1699 ms 95684 KB Output is correct
40 Correct 1769 ms 95852 KB Output is correct
41 Correct 1765 ms 95740 KB Output is correct
42 Correct 1802 ms 95648 KB Output is correct
43 Correct 1656 ms 95596 KB Output is correct
44 Correct 1666 ms 95468 KB Output is correct
45 Correct 1677 ms 95340 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 86764 KB Output is correct
2 Correct 264 ms 85228 KB Output is correct
3 Correct 263 ms 85228 KB Output is correct
4 Correct 262 ms 85212 KB Output is correct
5 Correct 265 ms 85228 KB Output is correct
6 Correct 268 ms 85228 KB Output is correct
7 Correct 264 ms 85228 KB Output is correct
8 Correct 57 ms 84844 KB Output is correct
9 Correct 52 ms 84844 KB Output is correct
10 Correct 54 ms 84972 KB Output is correct
11 Correct 650 ms 86764 KB Output is correct
12 Correct 654 ms 86652 KB Output is correct
13 Correct 654 ms 86892 KB Output is correct
14 Correct 647 ms 86892 KB Output is correct
15 Correct 647 ms 87276 KB Output is correct
16 Correct 705 ms 86752 KB Output is correct
17 Correct 666 ms 86712 KB Output is correct
18 Correct 651 ms 86764 KB Output is correct
19 Correct 56 ms 84860 KB Output is correct
20 Correct 52 ms 84844 KB Output is correct
21 Correct 62 ms 84844 KB Output is correct
22 Correct 54 ms 84844 KB Output is correct
23 Correct 51 ms 84844 KB Output is correct
24 Correct 52 ms 84844 KB Output is correct
25 Correct 53 ms 84972 KB Output is correct
26 Correct 55 ms 84844 KB Output is correct
27 Correct 56 ms 84844 KB Output is correct
28 Correct 65 ms 84844 KB Output is correct
29 Correct 53 ms 84852 KB Output is correct
30 Correct 55 ms 84972 KB Output is correct
31 Correct 55 ms 84844 KB Output is correct
32 Correct 54 ms 84844 KB Output is correct
33 Correct 57 ms 84972 KB Output is correct
34 Correct 56 ms 84972 KB Output is correct
35 Correct 55 ms 84972 KB Output is correct
36 Correct 56 ms 84972 KB Output is correct
37 Correct 55 ms 84844 KB Output is correct
38 Correct 61 ms 84844 KB Output is correct
39 Correct 53 ms 84844 KB Output is correct
40 Correct 562 ms 87276 KB Output is correct
41 Correct 193 ms 87660 KB Output is correct
42 Correct 189 ms 87724 KB Output is correct
43 Correct 171 ms 87532 KB Output is correct
44 Correct 203 ms 87788 KB Output is correct
45 Correct 209 ms 87788 KB Output is correct
46 Correct 210 ms 87788 KB Output is correct
47 Correct 51 ms 84844 KB Output is correct
48 Correct 54 ms 84844 KB Output is correct
49 Correct 54 ms 84948 KB Output is correct
50 Correct 652 ms 91756 KB Output is correct
51 Correct 579 ms 93240 KB Output is correct
52 Correct 695 ms 91796 KB Output is correct
53 Correct 664 ms 91784 KB Output is correct
54 Correct 588 ms 93288 KB Output is correct
55 Correct 638 ms 93804 KB Output is correct
56 Correct 624 ms 93676 KB Output is correct
57 Correct 633 ms 93804 KB Output is correct
58 Correct 560 ms 93140 KB Output is correct
59 Correct 549 ms 93236 KB Output is correct
60 Correct 560 ms 93168 KB Output is correct
61 Correct 1380 ms 86412 KB Output is correct
62 Correct 334 ms 88556 KB Output is correct
63 Correct 339 ms 88300 KB Output is correct
64 Correct 340 ms 88300 KB Output is correct
65 Correct 351 ms 88300 KB Output is correct
66 Correct 348 ms 88428 KB Output is correct
67 Correct 350 ms 88300 KB Output is correct
68 Correct 51 ms 84844 KB Output is correct
69 Correct 55 ms 84972 KB Output is correct
70 Correct 51 ms 84844 KB Output is correct
71 Correct 1383 ms 92912 KB Output is correct
72 Correct 1397 ms 95992 KB Output is correct
73 Correct 1388 ms 92852 KB Output is correct
74 Correct 1430 ms 92860 KB Output is correct
75 Correct 1393 ms 95852 KB Output is correct
76 Correct 1416 ms 96268 KB Output is correct
77 Correct 1408 ms 96236 KB Output is correct
78 Correct 1408 ms 96260 KB Output is correct
79 Correct 1357 ms 95980 KB Output is correct
80 Correct 1342 ms 96108 KB Output is correct
81 Correct 1349 ms 96108 KB Output is correct
82 Correct 1735 ms 95800 KB Output is correct
83 Correct 324 ms 88172 KB Output is correct
84 Correct 317 ms 88172 KB Output is correct
85 Correct 319 ms 88172 KB Output is correct
86 Correct 330 ms 88172 KB Output is correct
87 Correct 328 ms 88428 KB Output is correct
88 Correct 331 ms 88300 KB Output is correct
89 Correct 49 ms 84844 KB Output is correct
90 Correct 49 ms 84844 KB Output is correct
91 Correct 48 ms 84972 KB Output is correct
92 Correct 1768 ms 92804 KB Output is correct
93 Correct 1659 ms 95468 KB Output is correct
94 Correct 1752 ms 92908 KB Output is correct
95 Correct 1747 ms 92780 KB Output is correct
96 Correct 1319 ms 92652 KB Output is correct
97 Correct 1315 ms 92788 KB Output is correct
98 Correct 1318 ms 92780 KB Output is correct
99 Correct 1699 ms 95684 KB Output is correct
100 Correct 1769 ms 95852 KB Output is correct
101 Correct 1765 ms 95740 KB Output is correct
102 Correct 1802 ms 95648 KB Output is correct
103 Correct 1656 ms 95596 KB Output is correct
104 Correct 1666 ms 95468 KB Output is correct
105 Correct 1677 ms 95340 KB Output is correct
106 Correct 2287 ms 96364 KB Output is correct
107 Correct 453 ms 88300 KB Output is correct
108 Correct 420 ms 88300 KB Output is correct
109 Correct 421 ms 88300 KB Output is correct
110 Correct 50 ms 84844 KB Output is correct
111 Correct 47 ms 84844 KB Output is correct
112 Correct 47 ms 84844 KB Output is correct
113 Correct 1792 ms 95852 KB Output is correct
114 Correct 1760 ms 95596 KB Output is correct
115 Correct 1776 ms 95340 KB Output is correct
116 Correct 1648 ms 95468 KB Output is correct
117 Correct 2270 ms 96492 KB Output is correct
118 Correct 1680 ms 95444 KB Output is correct
119 Correct 1659 ms 95692 KB Output is correct
120 Correct 616 ms 94060 KB Output is correct
121 Correct 609 ms 93804 KB Output is correct
122 Correct 609 ms 93944 KB Output is correct
123 Correct 544 ms 93036 KB Output is correct
124 Correct 547 ms 93292 KB Output is correct
125 Correct 543 ms 93164 KB Output is correct
126 Correct 2260 ms 93576 KB Output is correct
127 Correct 2251 ms 93216 KB Output is correct
128 Correct 2290 ms 96748 KB Output is correct
129 Correct 2263 ms 93192 KB Output is correct
130 Correct 1493 ms 93420 KB Output is correct
131 Correct 1492 ms 93324 KB Output is correct
132 Correct 1480 ms 93292 KB Output is correct
133 Correct 2283 ms 96708 KB Output is correct
134 Correct 2288 ms 96364 KB Output is correct
135 Correct 2276 ms 96364 KB Output is correct
136 Correct 419 ms 88380 KB Output is correct
137 Correct 412 ms 88300 KB Output is correct
138 Correct 413 ms 88428 KB Output is correct