Submission #1181903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181903		mehmetkagan	Progression (NOI20_progression)	C++20	0 / 100	3097 ms	1114112 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 3e5 + 5;
int a[N], d[N];

struct Node {
    int l, r, len;
    int lval, rval;
    int lrun, rrun, mrun;
    Node *left, *right;

    Node(int l, int r): l(l), r(r), len(r - l + 1), left(nullptr), right(nullptr) {
        lval = rval = lrun = rrun = mrun = 0;
    }

    void merge() {
        lval = left->lval;
        rval = right->rval;
        lrun = left->lrun;
        rrun = right->rrun;
        mrun = max(left->mrun, right->mrun);
        if (left->rval == right->lval) {
            if (left->lrun == left->len) lrun += right->lrun;
            if (right->rrun == right->len) rrun += left->rrun;
            mrun = max(mrun, left->rrun + right->lrun);
        }
    }
};

Node* build(int l, int r) {
    Node* node = new Node(l, r);
    if (l == r) {
        node->lval = node->rval = d[l];
        node->lrun = node->rrun = node->mrun = 1;
        return node;
    }
    int m = (l + r) / 2;
    node->left = build(l, m);
    node->right = build(m + 1, r);
    node->merge();
    return node;
}

void point_update(Node* node, int pos, int val) {
    if (node->l == node->r) {
        node->lval = node->rval = val;
        node->lrun = node->rrun = node->mrun = 1;
        return;
    }
    int m = (node->l + node->r) / 2;
    if (pos <= m) point_update(node->left, pos, val);
    else point_update(node->right, pos, val);
    node->merge();
}

Node query(Node* node, int l, int r) {
    if (l <= node->l && node->r <= r) return *node;
    int m = (node->l + node->r) / 2;
    if (r <= m) return query(node->left, l, r);
    if (l > m) return query(node->right, l, r);
    Node res(0, 0);
    Node left = query(node->left, l, r);
    Node right = query(node->right, l, r);
    res.left = &left;
    res.right = &right;
    res.len = left.len + right.len;
    res.merge();
    return res;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
    Node* root = build(1, n - 1);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1 || t == 2) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            for (int i = l; i <= r; i++) {
                int val = s + (i - l) * c;
                if (t == 1) a[i] += val;
                else a[i] = val;
            }
            for (int i = max(1LL, l - 1); i <= min(n - 1, r); i++) {
                d[i] = a[i + 1] - a[i];
                point_update(root, i, d[i]);
            }
        } else {
            int l, r;
            cin >> l >> r;
            if (l == r) cout << 1 << '\n';
            else cout << query(root, l, r - 1).mrun + 1 << '\n';
        }
    }

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17