Submission #736806

#	Time	Username	Problem	Language	Result	Execution time	Memory
736806		Ronin13	Progression (NOI20_progression)	C++14	68 / 100	1085 ms	153588 KiB

Progression

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 500001;

struct node{
    ll x, y;
    ll pr, suf;
    ll sum, lazy, lazy1;
    bool good = false;
    ll ans = 0;
    node(){
        x = y = 0;
        pr = suf = 0;
        sum = lazy1 = 0;
        lazy = -9e18;
        ans = 0;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.pr = a.pr;
    c.suf = b.suf;
    c.x = a.x;
    c.y = b.y;
    if(a.good){
        if(b.x == a.x) c.pr += b.pr;
    }
    if(b.good){
        if(a.y == b.y) c.suf += a.suf;
    }
    if(a.good && b.good && a.x == b.x)
        c.good = true;
    c.ans = max(a.ans, b.ans);
    if(a.y == b.x){
        c.ans = max(c.ans, a.suf + b.pr);
    }
    return c;
}
//lazy minichebis lazy1 damatebis
void push1(int v, int l, int r){
    if(t[v].lazy == -9e18)return;
    t[v * 2].lazy = t[v].lazy;
    t[v * 2].lazy1 = 0;
    t[v * 2 + 1].lazy = t[v].lazy;
    t[v * 2 + 1].lazy1 = 0;
    int m = (l + r) /2;
    t[v * 2].sum = (ll)(m - l + 1) * t[v].lazy;
    t[v * 2 + 1].sum = (ll)(r - m) * t[v].lazy;
    t[v * 2].good = true;
    t[v * 2].pr = t[v * 2].suf = m - l + 1;
    t[v * 2].x = t[v * 2].y = t[v].lazy;
    t[v * 2 + 1].good = true;
    t[v * 2 + 1].pr = t[v * 2 + 1].suf = r - m;
    t[v * 2 + 1].x = t[v * 2 + 1].y = t[v].lazy;
    t[v].lazy = -9e18;
    t[v].lazy1 = 0;
}

void push2(int v, int l, int r){
    if(t[v].lazy1 == 0) return;
    ll m = (l + r) / 2;
    if(t[v * 2].lazy != -9e18) t[v * 2].lazy += t[v].lazy1;
    if(t[v * 2 + 1].lazy != -9e18) t[v * 2 + 1].lazy += t[v].lazy1;
    t[v * 2].lazy1 += t[v].lazy1;
    t[v * 2 + 1].lazy1 += t[v].lazy1;
    t[v * 2].x += t[v].lazy1;
    t[v * 2].y += t[v].lazy1;
    t[v * 2 + 1].x += t[v].lazy1;
    t[v * 2 + 1].y += t[v].lazy1;
    t[v * 2].sum += t[v].lazy1 * (ll)(m - l + 1);
    t[v * 2 + 1].sum += t[v].lazy1 * (ll)(r - m);
    t[v].lazy1 = 0;
}

void updran1(int v, int l, int r, int st, int fin, ll val){//minicheba intervalze
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v].sum = val * (ll)(r - l + 1);
        t[v].x = t[v].y = val;
        t[v].pr = t[v].suf = r - l + 1;
        t[v].lazy = val;
        t[v].lazy1 = 0;
        t[v].good = true;
        t[v].ans = r - l + 1;
        return;
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    updran1(2 * v, l, m, st, fin, val);
    updran1(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}


void updran2(int v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v].sum += val * (ll)(r - l + 1);
        t[v].x += val;
        t[v].y += val;
        if(t[v].lazy != -9e18) t[v].lazy += val;
        t[v].lazy1 += val;
        return;
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    updran2(2 * v, l, m, st, fin, val);
    updran2(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}


ll getsum(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin)
        return t[v].sum;
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    return getsum(2 * v, l, m,st, fin) + getsum(2 * v + 1, m + 1, r, st, fin);
}

node getans(int v, int l, int r, int tl, int tr){
    if(l == tl && r == tr){
        return t[v];
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    if(tl > m)
        return getans(2 * v + 1, m + 1, r, tl, tr);
    if(tr <= m)
        return getans(2 * v, l, m, tl, tr);
    return merg(getans(2 * v, l, m, tl, m), getans(2 * v + 1, m + 1, r, m + 1, tr));
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    ll a[n + 1];
    for(int i = 1; i<= n; ++i){
        cin >> a[i];
    }
    for(int i = n; i >= 2; i--){
        updran1(1, 1, n, i - 1, i - 1, a[i] - a[i - 1]);
    }

    while(q--){
        int t; cin >> t;
        if(t == 3){
            int l, r; cin >> l >> r;
            if(l == r) cout << 1 << "\n";
            else
            cout << getans(1, 1, n, l, r - 1).ans + 1 << "\n";
        }
        if(t == 1){
            ll l, r, s, c; cin >> l >> r >> s >> c;
            if(l > 1){
                updran2(1, 1, n, l - 1, l - 1, s);
            }
            else a[1] += s;

            ll val = s + c * (r - l);

            if(r != n)updran2(1, 1, n, r, r, -val);
            updran2(1,1, n, l, r - 1, c);
        }
        if(t == 2){
            ll l, r, s, c; cin >> l >> r >> s >> c;

            ll y =  getsum(1, 1, n, 1, r) + a[1];
            if(l > 1){
                ll x = getsum(1, 1, n, 1, l - 2) + a[1];
                updran1(1, 1, n, l - 1, l - 1, s - x);
            }

            if(l == 1){
                a[1] = s;
            }
            updran1(1, 1, n, l, r - 1, c);
            if(r < n){
                ll x = y;
                updran1(1, 1, n, r, r, x - s  - c * (r - l));
            }
        }
    }
    return 0;
}

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