Submission #813595

#	Time	Username	Problem	Language	Result	Execution time	Memory
813595		danikoynov	Progression (NOI20_progression)	C++14	61 / 100	3056 ms	63748 KiB

Progression

#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
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17