oj.uz

Submission #813595

# Submission time Handle Problem Language Result Execution time Memory
813595 2023-08-07T23:42:40 Z danikoynov Progression (NOI20_progression) C++14
61 / 100
 3000 ms 63748 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

struct node
{
    int left_value, right_value;
    int left_len, right_len;
    int longest, fat;

    node()
    {
        left_value = right_value = 0;
        left_len = right_len = 0;
        longest = 0;
        fat = 0;
    }
};

node merge_nodes(node lf, node rf)
{
    node cur;
    cur.left_value = lf.left_value;
    cur.right_value = rf.right_value;
    cur.left_len = lf.left_len;
    cur.right_len = rf.right_len;
    cur.longest = max(lf.longest, rf.longest);
    if (lf.right_value == rf.left_value)
    {
        ///cout << "merge " << " " << lf.right_len << " " << rf.left_len << endl;
        cur.longest = max(cur.longest, lf.right_len + rf.left_len);
        if (lf.fat)
            cur.left_len += rf.left_len;
        if (rf.fat)
            cur.right_len += lf.right_len;
        if (lf.fat && rf.fat)
        {
            cur.fat = true;
            cur.left_len = cur.longest;
            cur.right_len = cur.longest;
        }
        else
            cur.fat = false;
    }
    return cur;
}

node tree[4 * maxn];

ll lazy_add[4 * maxn], lazy_set[4 * maxn], tag[4 * maxn];

void push_lazy(int root, int left, int right)
{
    if (tag[root])
    {
        tree[root].left_value = tree[root].right_value = lazy_set[root];
        tree[root].left_len = tree[root].right_len = tree[root].longest = right - left + 1;
        tree[root].fat = true;
        if (left != right)
        {
            tag[root * 2] = tag[root * 2 + 1] = 1;
            lazy_set[root * 2] = lazy_set[root * 2 + 1] = lazy_set[root];
            lazy_add[root * 2] = lazy_add[root * 2 + 1] = 0;
        }
        tag[root] = 0;
        lazy_set[root] = 0;
    }

    tree[root].left_value += lazy_add[root];
    tree[root].right_value += lazy_add[root];

    if (left != right)
    {
        lazy_add[root * 2] += lazy_add[root];
        lazy_add[root * 2 + 1] += lazy_add[root];
    }

    lazy_add[root] = 0;
}
void update_set(int root, int left, int right, int qleft, int qright, ll value)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        tag[root] = 1;
        lazy_set[root] = value;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_set(root * 2, left, mid, qleft, qright, value);
    update_set(root * 2 + 1, mid + 1, right, qleft, qright, value);
    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);

    ///cout << "back " << tree[root].left_value << " " << tree[root].right_value << endl;
    ///cout << left << " " << right << " " << tree[root * 2].right_value << " " << tree[root * 2 + 1].left_value << endl;
}
void update_add(int root, int left, int right, int qleft, int qright, ll value)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        ///cout << "update add " << left << " " << right << endl;
        lazy_add[root] = value;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_add(root * 2, left, mid, qleft, qright, value);
    update_add(root * 2 + 1, mid + 1, right, qleft, qright, value);
    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);

}

node query(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);
    if (left == qleft && right == qright)
        return tree[root];

    int mid = (left + right) / 2;
    if (qright <= mid)
        return query(root * 2, left, mid, qleft, qright);

    if (qleft > mid)
        return query(root * 2 + 1, mid + 1, right, qleft, qright);

    return merge_nodes(query(root * 2, left, mid, qleft, mid),
                       query(root * 2 + 1, mid + 1, right, mid + 1, qright));
}

int n, q;
ll d[maxn], b[maxn];
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].left_value = tree[root].right_value = b[left];
        tree[root].left_len = tree[root].right_len = 1;
        tree[root].fat = true;
        tree[root].longest = 1;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    ///cout << left << " : " << right << " " << tree[root].longest << endl;
}


void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> d[i], b[i] = d[i] - d[i - 1];

    build_tree(1, 1, n);
    for (int i = 1; i <= q; i ++)
    {
        int type, l, r, s, c;
        cin >> type >> l >> r;
        if (type == 1)
        {
            cin >> s >> c;
            for (int j = l; j <= r; j ++)
            {
                d[j] += s + (j - l) * c;
                b[j] += c;
            }
            update_add(1, 1, n, l, r, c);
            update_set(1, 1, n, l, l, d[l] - d[l - 1]);
            if (r != n)
                update_set(1, 1, n, r + 1, r + 1, d[r + 1] - d[r]);
                ///cout << "------------------" << endl;
            b[l] = d[l] - d[l - 1];
            b[r + 1] = d[r + 1] - d[r];
        }
        else if (type == 2)
        {
            cin >> s >> c;
            for (int j = l; j <= r; j ++)
            {
                d[j] = s + (j - l) * c;
                b[j] = c;
            }
            update_set(1, 1, n, l, r, c);
            update_set(1, 1, n, l, l, d[l] - d[l - 1]);
            if (r != n)
                update_set(1, 1, n, r + 1, r + 1, d[r + 1] - d[r]);
            b[l] = d[l] - d[l - 1];
            b[r + 1] = d[r + 1] - d[r];
        }
        else
        {
            if (l == r)
            {
                cout << 1 << endl;
                continue;
            }
            node cur = query(1, 1, n, l + 1, r);
            cout << cur.longest + 1 << endl;
            /**int len = 1, ans = 0;
            for (int j = l + 2; j <= r; j ++)
            {
                if (b[j] == b[j - 1])
                    len ++;
                else
                {
                    ans = max(ans, len);
                    len = 1;
                }
            }
            ans = max(ans, len);
            cout << ans + 1 << endl;*/
        }

        /**for (int j = 1; j <= n; j ++)
            cout << d[j] << " ";
        cout << endl;*/
    }
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
10 3
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10

*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 33912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28516 KB Output is correct
2 Correct 14 ms 28512 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 14 ms 28520 KB Output is correct
5 Correct 14 ms 28548 KB Output is correct
6 Correct 16 ms 28508 KB Output is correct
7 Correct 14 ms 28500 KB Output is correct
8 Correct 15 ms 28520 KB Output is correct
9 Correct 15 ms 28500 KB Output is correct
10 Correct 17 ms 28524 KB Output is correct
11 Correct 18 ms 28528 KB Output is correct
12 Correct 18 ms 28564 KB Output is correct
13 Correct 14 ms 28512 KB Output is correct
14 Correct 15 ms 28588 KB Output is correct
15 Correct 16 ms 28628 KB Output is correct
16 Correct 17 ms 28584 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 15 ms 28604 KB Output is correct
19 Correct 15 ms 28516 KB Output is correct
20 Correct 17 ms 28496 KB Output is correct
21 Correct 17 ms 28556 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 42688 KB Output is correct
2 Correct 85 ms 29404 KB Output is correct
3 Correct 75 ms 29276 KB Output is correct
4 Correct 69 ms 29292 KB Output is correct
5 Correct 99 ms 29420 KB Output is correct
6 Correct 83 ms 29336 KB Output is correct
7 Correct 86 ms 29424 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 15 ms 28416 KB Output is correct
10 Correct 13 ms 28512 KB Output is correct
11 Correct 262 ms 46240 KB Output is correct
12 Correct 223 ms 48524 KB Output is correct
13 Correct 267 ms 47068 KB Output is correct
14 Correct 275 ms 47108 KB Output is correct
15 Correct 253 ms 48468 KB Output is correct
16 Correct 300 ms 49036 KB Output is correct
17 Correct 283 ms 48972 KB Output is correct
18 Correct 318 ms 49080 KB Output is correct
19 Correct 246 ms 48416 KB Output is correct
20 Correct 238 ms 48344 KB Output is correct
21 Correct 239 ms 48368 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 54144 KB Output is correct
2 Correct 159 ms 28960 KB Output is correct
3 Correct 155 ms 28968 KB Output is correct
4 Correct 152 ms 28932 KB Output is correct
5 Correct 159 ms 28952 KB Output is correct
6 Correct 158 ms 28904 KB Output is correct
7 Correct 157 ms 28960 KB Output is correct
8 Correct 14 ms 28508 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 618 ms 58568 KB Output is correct
12 Correct 660 ms 63528 KB Output is correct
13 Correct 628 ms 60344 KB Output is correct
14 Correct 615 ms 60276 KB Output is correct
15 Correct 616 ms 63536 KB Output is correct
16 Correct 639 ms 63636 KB Output is correct
17 Correct 648 ms 63692 KB Output is correct
18 Correct 639 ms 63748 KB Output is correct
19 Correct 613 ms 63588 KB Output is correct
20 Correct 637 ms 63656 KB Output is correct
21 Correct 646 ms 63480 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 42688 KB Output is correct
2 Correct 85 ms 29404 KB Output is correct
3 Correct 75 ms 29276 KB Output is correct
4 Correct 69 ms 29292 KB Output is correct
5 Correct 99 ms 29420 KB Output is correct
6 Correct 83 ms 29336 KB Output is correct
7 Correct 86 ms 29424 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 15 ms 28416 KB Output is correct
10 Correct 13 ms 28512 KB Output is correct
11 Correct 262 ms 46240 KB Output is correct
12 Correct 223 ms 48524 KB Output is correct
13 Correct 267 ms 47068 KB Output is correct
14 Correct 275 ms 47108 KB Output is correct
15 Correct 253 ms 48468 KB Output is correct
16 Correct 300 ms 49036 KB Output is correct
17 Correct 283 ms 48972 KB Output is correct
18 Correct 318 ms 49080 KB Output is correct
19 Correct 246 ms 48416 KB Output is correct
20 Correct 238 ms 48344 KB Output is correct
21 Correct 239 ms 48368 KB Output is correct
22 Execution timed out 3056 ms 58100 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 33912 KB Time limit exceeded
2 Halted 0 ms 0 KB -