Submission #1241636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241636		trufanov.p	Progression (NOI20_progression)	C++20	0 / 100	833 ms	1114112 KiB

Progression

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>
#include <set>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

struct Node {
    int maxseg; //
    ll maxsegval; //
    int maxpref; //
    ll first; //
    int maxsuff; //
    ll last; //
    ll addval; //
    ll setval; //
    bool hasset; //
    int len; //
    bool neutral; //
    ll summ;
    Node() :addval(0), setval(0), hasset(false), len(0), neutral(false), summ(0) {}
    Node(bool _) :neutral(true) {}
    Node(ll x) {
        maxseg = 1;
        maxsegval = x;
        maxpref = 1;
        first = x;
        maxsuff = 1;
        last = x;
        addval = 0;
        setval = 0;
        hasset = false;
        len = 1;
        neutral = false;
        summ = 0;
    }
};

void push(int v, vector<Node>& t) {
    if (!t[v].hasset) {
        t[2 * v + 1].addval += t[v].addval;
        t[2 * v + 2].addval += t[v].addval;
        t[v].addval = 0;
    } else {
        t[2 * v + 1].setval = t[v].setval;
        t[2 * v + 1].addval = t[v].addval;
        t[2 * v + 1].hasset = true;
        t[2 * v + 2].setval = t[v].setval;
        t[2 * v + 2].addval = t[v].addval;
        t[2 * v + 2].hasset = true;
        t[v].setval = 0;
        t[v].addval = 0;
        t[v].hasset = false;
    }
}

Node selfpush(const Node& a) {
    Node b = a;
    if (!a.hasset) {
        b.first += b.addval;
        b.last += b.addval;
        b.maxsegval += b.addval;
        b.summ += b.addval * b.len;
        b.addval = 0;
    } else {
        b.first = b.setval + b.addval;
        b.last = b.setval + b.addval;
        b.maxsegval = b.setval + b.addval;
        b.maxpref = b.len;
        b.maxsuff = b.len;
        b.maxseg = b.len;
        b.summ = (b.setval + b.addval) * b.len;
        b.hasset = 0;
        b.setval = 0;
        b.addval = 0;
    }
    return b;
}

Node unite(const Node& a_, const Node& b_) {
    Node a = selfpush(a_), b = selfpush(b_);
    if (a_.neutral) {
        return b;
    } else if (b_.neutral) {
        return a;
    }
    Node c;
    c.neutral = false;
    c.len = a.len + b.len;
    c.summ = a.summ + b.summ;
    /*ll afirstreal = (a.hasset ? a.setval + a.addval : a.first + a.addval);
    ll alastreal = (a.hasset ? a.setval + a.addval : a.last + a.addval);
    ll bfirstreal = (b.hasset ? b.setval + b.addval : b.first + b.addval);
    ll blastreal = (b.hasset ? b.setval + b.addval : b.last + b.addval);
    c.first = afirstreal;
    c.maxpref = a.maxpref + (a.maxpref == a.len && afirstreal == bfirstreal ? b.maxpref : 0);
    c.last = blastreal;
    c.maxsuff = b.maxsuff + (b.maxsuff == b.len && blastreal == alastreal ? a.maxsuff : 0);
    ll amaxreal = (a.hasset ? a.setval + a.addval : a.maxsegval + a.addval);
    ll bmaxreal = (b.hasset ? b.setval + b.addval : b.maxsegval + b.addval);
    if (a.maxseg > b.maxseg) {
        c.maxseg = a.maxseg;
        c.maxsegval = amaxreal;
    } else {
        c.maxseg = b.maxseg;
        c.maxsegval = bmaxreal;
    }
    if (alastreal == bfirstreal && a.maxsuff + b.maxpref > c.maxseg) {
        c.maxseg = a.maxsuff + b.maxpref;
        c.maxsegval = alastreal;
    }*/
    c.first = a.first;
    c.maxpref = a.maxpref + (a.maxpref == a.len && a.first == b.first ? b.maxpref : 0);
    c.last = b.last;
    c.maxsuff = b.maxsuff + (b.maxsuff == b.len && b.last == a.last ? a.maxsuff : 0);
    if (a.maxseg > b.maxseg) {
        c.maxseg = a.maxseg;
        c.maxsegval = a.maxsegval;
    } else {
        c.maxseg = b.maxseg;
        c.maxsegval = b.maxsegval;
    }
    if (a.last == b.first && a.maxsuff + b.maxpref > c.maxseg) {
        c.maxseg = a.maxsuff + b.maxpref;
        c.maxsegval = a.last;
    }
    return c;
}

void build(int v, int l, int r, vector<Node>& t, const vector<ll>& a) {
    if (l == r - 1) {
        t[v] = Node(a[l]);
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m, t, a);
    build(2 * v + 2, m, r, t, a);
    t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}

Node query(int v, int l, int r, int askl, int askr, vector<Node>& t) {
    if (l >= askr || r <= askl) {
        return Node(true);
    }
    if (l >= askl && r <= askr) {
        return selfpush(t[v]);
    }
    push(v, t);
    int m = (l + r) / 2;
    auto ans_left = query(2 * v + 1, l, m, askl, askr, t);
    auto ans_right = query(2 * v + 2, m, r, askl, askr, t);
    t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
    return unite(ans_left, ans_right);
}

void range_add(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) {
    if (l >= askr || r <= askl) {
        return;
    }
    if (l >= askl && r <= askr) {
        t[v].addval += val;
        return;
    }
    push(v, t);
    int m = (l + r) / 2;
    range_add(2 * v + 1, l, m, askl, askr, val, t);
    range_add(2 * v + 2, m, r, askl, askr, val, t);
    t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}

void range_set(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) {
    if (l >= askr || r <= askl) {
        return;
    }
    if (l >= askl && r <= askr) {
        t[v].hasset = true;
        t[v].setval = val;
        t[v].addval = 0;
        return;
    }
    push(v, t);
    int m = (l + r) / 2;
    range_set(2 * v + 1, l, m, askl, askr, val, t);
    range_set(2 * v + 2, m, r, askl, askr, val, t);
    t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}

ll get_elem(int i, int n, vector<Node>& t) {
    return query(0, 0, n, i, i + 1, t).maxsegval;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> orig(n);
    for (int i = 0; i < n; ++i) {
        cin >> orig[i];
    }
    ll realfirst = orig[0];
    vector<ll> diff;
    for (int i = 1; i < n; ++i) {
        diff.push_back(orig[i] - orig[i - 1]);
    }
    vector<Node> t(4 * (n - 1));
    build(0, 0, n - 1, t, diff);
    for (int _ = 0; _ < q; ++_) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            if (l == 1) {
                realfirst += s;
            }
            //l--, r--;
            l -= 2, r -= 2;
            if (l >= 0) {
                range_add(0, 0, n - 1, l, l + 1, s, t);
            }
            range_add(0, 0, n - 1, l + 1, r + 1, c, t);
            if (r + 1 < n) {
                range_add(0, 0, n - 1, r + 1, r + 2, -(s + (r - l) * c), t);
            }
        } else if (type == 2) {
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            if (l == 1) {
                realfirst = s;
            }
            //l--, r--;
            l -= 2, r -= 2;
            ll realr = query(0, 0, n - 1, 0, r + 1, t).summ + realfirst;
            if (l >= 0) {
                ll prv = (l == 0 ? 0ll : get_elem(l - 1, n - 1, t));
                range_set(0, 0, n - 1, l, l + 1, s - prv, t);
            }
            range_set(0, 0, n - 1, l + 1, r + 1, c, t);
            if (r + 1 < n) {
                ll nxt = get_elem(r + 1, n - 1, t);
                range_add(0, 0, n - 1, r + 1, r + 2, realr - (s + (r - l) * c), t);
            }
        } else {
            int l, r;
            cin >> l >> r;
            //l--, r--;
            l -= 1, r -= 2;
            cout << query(0, 0, n - 1, l, r + 1, t).maxseg + 1 << '\n';
        }
    }
}

/*
10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10
*/

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