Submission #270694

#	Time	Username	Problem	Language	Result	Execution time	Memory
270694		doowey	Progression (NOI20_progression)	C++14	100 / 100	1181 ms	71032 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
const ll inf = (ll)1e12;
const ll F = -inf;

bool debug;

struct Node{
    ll sigma;
    ll set_l;
    ll add_l;
    int siz;
    ll lef_val;
    ll rig_val;
    int answer;
    int ans_pref;
    int ans_suff;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    if(T[node].set_l != (ll)1e18){
        T[node].set_l += T[node].add_l;
        T[node].sigma = T[node].siz * 1ll * T[node].set_l;
        T[node].lef_val = T[node].set_l;
        T[node].rig_val = T[node].set_l;
        T[node].answer = T[node].siz;
        T[node].ans_pref = T[node].siz;
        T[node].ans_suff = T[node].siz;
        if(cl != cr){
            T[node * 2].set_l = T[node].set_l;
            T[node * 2].add_l = 0;
        }
        if(cl != cr){
            T[node * 2 + 1].set_l = T[node].set_l;
            T[node * 2 + 1].add_l = 0;
        }
        T[node].set_l = (ll)1e18;
        T[node].add_l = 0;
    }
    else if(T[node].add_l != 0){
        T[node].sigma += T[node].siz * 1ll * T[node].add_l;
        T[node].lef_val += T[node].add_l;
        T[node].rig_val += T[node].add_l;
        if(cl != cr)T[node * 2].add_l += T[node].add_l;
        if(cl != cr)T[node * 2 + 1].add_l += T[node].add_l;
        T[node].add_l = 0ll;
    }
}

Node unite(Node A, Node B){
    Node ret;
    ret.sigma = A.sigma + B.sigma;
    ret.add_l = 0ll;
    ret.set_l = (ll)1e18;
    ret.siz = A.siz + B.siz;
    ret.answer = max(A.answer, B.answer);
    ret.lef_val = A.lef_val;
    ret.rig_val = B.rig_val;
    ret.ans_pref = A.ans_pref;
    ret.ans_suff = B.ans_suff;
    if(A.rig_val == B.lef_val){
        ret.answer = max(ret.answer, A.ans_suff + B.ans_pref);
        if(A.ans_pref == A.siz) ret.ans_pref += B.ans_pref;
        if(B.ans_suff == B.siz) ret.ans_suff += A.ans_suff;
    }
    return ret;
}

void upd1(int node, int cl, int cr, int tl, int tr, ll x){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].set_l = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd1(node * 2, cl, mid, tl, tr, x);
    upd1(node * 2 + 1, mid + 1, cr, tl, tr, x);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

void upd2(int node, int cl, int cr, int tl, int tr, ll x){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].add_l = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd2(node * 2, cl, mid, tl, tr, x);
    upd2(node * 2 + 1, mid + 1, cr, tl, tr, x);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

ll get_sum(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return 0ll;
    if(cl >= tl && cr <= tr){
        return T[node].sigma;
    }
    int mid = (cl + cr) / 2;
    return get_sum(node * 2, cl, mid, tl, tr) + get_sum(node * 2 + 1, mid + 1, cr, tl, tr);
}

Node cur;
bool has;

void query(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(tl > tr) return;
    if(cr < tl) return;
    if(cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(!has) {
            cur = T[node];
            has=true;
        }
        else{
            cur = unite(cur, T[node]);
        }
        return;
    }
    int mid = (cl + cr) / 2;
    query(node * 2, cl, mid, tl, tr);
    query(node * 2 + 1, mid + 1, cr, tl, tr);
}

int n;
ll A[N];

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node] = {A[cl], (ll)1e18, 0ll,cr-cl+1,A[cl],A[cl],1,1,1};
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

int main(){
    fastIO;
    int q;
    cin >> n >> q;
    A[0] = F;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
    }
    for(int i = n; i >= 1; i -- ){
        A[i] = A[i] - A[i - 1];
    }
    build(1, 0, n);
    int type;
    ll l, r, s, x;
    ll fb, fs;
    for(int i = 0 ; i < q; i ++ ){
        cin >> type;
        if(type == 1){
            cin >> l >> r >> s >> x;
            if(l + 1 <= r)upd2(1, 0, n, l + 1, r, x);
            upd2(1, 0, n, l, l, s);
            if(r + 1 <= n)
                upd2(1, 0, n, r + 1, r + 1, -(s + (r - l) * 1ll * x));
        }
        else if(type == 2){
            cin >> l >> r >> s >> x;
            fb = get_sum(1, 0, n, 0, l - 1);
            if(r < n) fs = get_sum(1, 0, n, 0, r + 1);
            upd1(1, 0, n, l, l, s - fb);
            if(l + 1 <= r)upd1(1, 0, n, l + 1, r, x);
            if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
        }
        else{
            cin >> l >> r;
            if(l == r){
                cout << 1 << "\n";
            }
            else{
                has=false;
                query(1, 0, n, l+1, r);
                cout << cur.answer + 1 << "\n";
            }
        }
    }
    return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:190:27: warning: 'fs' may be used uninitialized in this function [-Wmaybe-uninitialized]
  190 |             if(r < n) upd1(1, 0, n, r + 1, r + 1, fs-(s+(r-l)*x));
      |                       ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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