Submission #689415

#	Time	Username	Problem	Language	Result	Execution time	Memory
689415		ksjsjsjsjsjsjs	Progression (NOI20_progression)	C++17	100 / 100	1442 ms	92812 KiB

Progression

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define bg begin
#define ed end
#define ins insert
#define ers erase
#define mtp make_tuple
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed
#define ft front
#define bk back
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
struct Node {
    int l, ans;
    ll d, sum;
    pll p, s;
    Node() { l = ans = d = sum = p.st = p.nd = s.st = s.nd = 0; }
};
const int oo = 1e9 + 5;
const int T = 12e5 + 5;
int n, q;
Node tr[T];
pll la[T];
Node mrg(const Node &a, const Node &b) {
    if (!a.l) return b;
    if (!b.l) return a;
    Node ans = a;
    ans.l += b.l;
    ans.sum = a.sum + b.sum;
    ans.ans = max(a.ans, b.ans);
    if (b.d == a.s.st) ans.ans = max(1LL * ans.ans, a.s.nd + 1);
    if (b.d == b.p.st) ans.ans = max(1LL * ans.ans, b.p.nd + 1);
    if (a.s.st == b.p.st && b.p.st == b.d) ans.ans = max(1LL * ans.ans, a.s.nd + b.p.nd);
    if (a.p.nd == a.l) {
        if (a.l == 1) {
            ans.p = {b.d, 2};
            if (b.p.st == b.d) ans.p = {b.d, b.p.nd + 1};
        }
        else if (b.d == a.p.st) {
            ++ans.p.nd;
            if (b.p.st == b.d) ans.p.nd = a.l + b.p.nd;
        }
    }
    ans.s = b.s;
    if (b.s.nd == b.l) {
        if (b.l == 1) {
            ans.s = {b.d, 2};
            if (a.s.st == b.d)  ans.s = {b.d, a.s.nd + 1};
        }
        else if (b.s.st == b.d) {
            ++ans.s.nd;
            if (a.s.st == b.d) ans.s.nd = b.l + a.s.nd;
        }
    }
    return ans;
}
void build(int i, int l, int r) {
    if (l == r) {
        tr[i].l = 1;
        tr[i].d = 0;
        tr[i].ans = 1;
        tr[i].p = tr[i].s = {0, 1};
        return;
    }
    int mid = l + (r - l) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    tr[i] = mrg(tr[i * 2], tr[i * 2 + 1]);
}
void lazy(int i) {
    if (!la[i].st && !la[i].nd) return;
    if (!la[i].st) {
        tr[i].d += la[i].nd;
        tr[i].p.st += la[i].nd;
        tr[i].s.st += la[i].nd;
        tr[i].sum += 1LL * la[i].nd * tr[i].l;
    }
    else {
        tr[i].d = la[i].nd;
        tr[i].ans = tr[i].l;
        tr[i].p = tr[i].s = {la[i].nd, tr[i].l};
        tr[i].sum = 1LL * la[i].nd * tr[i].l;
    }
    if (tr[i].l > 1) {
        if (!la[i].st) {
            la[i * 2].nd += la[i].nd;
            la[i * 2 + 1].nd += la[i].nd;
        }
        else la[i * 2] = la[i * 2 + 1] = la[i];
    }
    la[i] = {0, 0};
}
void upd(int i, int l, int r, int ql, int qr, pll v) {
    lazy(i);
    if (r < ql || l > qr) return;
    if (ql <= l && r <= qr) {
        la[i] = v;
        lazy(i);
        return;
    }
    int mid = l + (r - l) / 2;
    upd(i * 2, l, mid, ql, qr, v);
    upd(i * 2 + 1, mid + 1, r, ql, qr, v);
    tr[i] = mrg(tr[i * 2], tr[i * 2 + 1]);
}
Node get(int i, int l, int r, int ql, int qr) {
    lazy(i);
    if (r < ql || l > qr) return Node();
    if (ql <= l && r <= qr) return tr[i];
    int mid = l + (r - l) / 2;
    return mrg(get(i * 2, l, mid, ql, qr), get(i * 2 + 1, mid + 1, r, ql, qr));
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n >> q;
    build(1, 1, n);
    int pred = 0;
    FOR(i, 1, n) {
        int d;
        cin >> d;
        upd(1, 1, n, i, i, {0, d - pred});
        pred = d;
    }
    WHILE(q--) {
        int t;
        cin >> t;
        if (t == 3) {
            int l, r;
            cin >> l >> r;
            cout << get(1, 1, n, l, r).ans << '\n';
        }
        else if (t == 1) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            upd(1, 1, n, l, l, {0, s});
            upd(1, 1, n, l + 1, r, {0, c});
            upd(1, 1, n, r + 1, r + 1, {0, -s - 1LL * (r - l) * c});
        }
        else {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            ll l1 = get(1, 1, n, 1, l - 1).sum, l2 = get(1, 1, n, 1, r + 1).sum;
            upd(1, 1, n, l, l, {1, s - l1});
            upd(1, 1, n, r + 1, r + 1, {1, l2 - s - 1LL * (r - l) * c});
            upd(1, 1, n, l + 1, r, {1, c});
        }
    }
    cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
/*
3 3
-1 0 -1
2 1 2 1 -1
2 3 3 -1 1
3 1 3

*/

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