Submission #1251421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251421		Geforgs	Progression (NOI20_progression)	C++20	100 / 100	1045 ms	88684 KiB

Progression

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bit>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

struct Node{
    ll pref=0, suf=0, prefVal=0, sufVal=0, res=0, push1=0, push2=-inf, sum=0;
    bool isConnected=true;
};

Node con(const Node& a, const Node& b){
    Node res;
    res.isConnected = false;
    if(a.isConnected and b.isConnected){
        if(a.sufVal == b.prefVal){
            res.isConnected = true;
            res.res = res.pref = res.suf = a.suf + b.pref;
        }
    }else if(a.isConnected){
        if(a.sufVal == b.prefVal){
            res.res = res.pref = a.suf + b.pref;
        }
    }else if(b.isConnected){
        if(a.sufVal == b.prefVal){
            res.res = res.suf = a.suf + b.pref;
        }
    }
    if(a.sufVal == b.prefVal){
        res.res = max(res.res, a.suf + b.pref);
    }
    res.res = max({res.res, a.res, b.res});
    res.prefVal = a.prefVal;
    res.sufVal = b.sufVal;
    res.pref = max(res.pref, a.pref);
    res.suf = max(res.suf, b.suf);
    res.sum = a.sum + b.sum;
    return res;
}

void build(ll id, ll l, ll r, vector<ll>& d, vector<Node>& a){
    if(l == r){
        if(l != 0){
            a[id].sum = a[id].prefVal = a[id].sufVal = d[l] - d[l-1];
            a[id].res = a[id].pref = a[id].suf = 1;
        }
        return;
    }
    ll m = (l+r)/2;
    build(2*id, l, m, d, a);
    build(2*id + 1, m+1, r, d, a);
    a[id] = con(a[2*id], a[2*id+1]);
}

void push(ll id, ll l, ll r, vector<Node>& a){
    ll m=(l+r)/2;
    if(a[id].push2 == -inf){
        a[2*id].sufVal += a[id].push1;
        a[2*id].prefVal += a[id].push1;
        a[2*id].push1 += a[id].push1;
        a[2*id].sum += (m - l + 1)*a[id].push1;
        a[2*id + 1].sufVal += a[id].push1;
        a[2*id + 1].prefVal += a[id].push1;
        a[2*id + 1].push1 += a[id].push1;
        a[2*id + 1].sum += (r - m)*a[id].push1;
        a[id].push1 = 0;
    }else{
        a[id].push2 += a[id].push1;
        a[2*id].push1 = 0;
        a[2*id].push2 = a[id].push2;
        a[2*id].res = a[2*id].suf = a[2*id].pref = m - l + 1;
        a[2*id].prefVal = a[2*id].sufVal = a[id].push2;
        a[2*id].isConnected = true;
        a[2*id].sum = (m - l + 1)*a[id].push2;
        a[2*id+1].push1 = 0;
        a[2*id+1].push2 = a[id].push2;
        a[2*id+1].res = a[2*id+1].suf = a[2*id+1].pref = r - m;
        a[2*id+1].prefVal = a[2*id+1].sufVal = a[id].push2;
        a[2*id+1].isConnected = true;
        a[2*id+1].sum = (r - m)*a[id].push2;
        a[id].push1 = 0;
        a[id].push2 = -inf;
    }
}

Node get(ll id, ll l, ll r, ll tl, ll tr, vector<Node>& a){
    if(r < tl or tr < l) return Node();
    if(tl <= l and r <= tr){
        return a[id];
    }
    push(id, l, r, a);
    ll m=(l+r)/2;
    return con(get(2*id, l, m, tl, tr, a), get(2*id+1, m+1, r, tl, tr, a));
}

void add(ll id, ll l, ll r, ll tl, ll tr, ll val, vector<Node>& a){
    if(r < tl or tr < l) return;
    if(tl <= l and r <= tr){
        a[id].prefVal += val;
        a[id].sufVal += val;
        a[id].push1 += val;
        a[id].sum += (r - l + 1)*val;
        return;
    }
    push(id, l, r, a);
    ll m=(l+r)/2;
    add(2*id, l, m, tl, tr, val, a);
    add(2*id+1, m+1, r, tl, tr, val, a);
    a[id] = con(a[2*id], a[2*id+1]);
}

void add(ll id, ll l, ll r, ll x, ll val, vector<Node>& a){
    if(l == r){
        a[id].prefVal += val;
        a[id].sufVal += val;
        a[id].push1 += val;
        a[id].sum += val;
        return;
    }
    push(id, l, r, a);
    ll m=(l+r)/2;
    if(x <= m){
        add(2*id, l, m, x, val, a);
    }else{
        add(2*id+1, m+1, r, x, val, a);
    }
    a[id] = con(a[2*id], a[2*id+1]);
}

void Set(ll id, ll l, ll r, ll tl, ll tr, ll val, vector<Node>& a){
    if(r < tl or tr < l) return;
    if(tl <= l and r <= tr){
        a[id].push1 = 0;
        a[id].push2 = val;
        a[id].prefVal = a[id].sufVal = val;
        a[id].res = a[id].pref = a[id].suf = r - l + 1;
        a[id].isConnected = true;
        a[id].sum = (r - l + 1)*val;
        return;
    }
    push(id, l, r, a);
    ll m=(l+r)/2;
    Set(2*id, l, m, tl, tr, val, a);
    Set(2*id+1, m+1, r, tl, tr, val, a);
    a[id] = con(a[2*id], a[2*id+1]);
}

void Set(ll id, ll l, ll r, ll x, ll val, vector<Node>& a){
    if(l == r){
        a[id].push1 = 0;
        a[id].push2 = val;
        a[id].prefVal = a[id].sufVal = val;
        a[id].res = a[id].pref = a[id].suf = 1;
        a[id].isConnected = true;
        a[id].sum = val;
        return;
    }
    push(id, l, r, a);
    ll m=(l+r)/2;
    if(x <= m){
        Set(2*id, l, m, x, val, a);
    }else{
        Set(2*id+1, m+1, r, x, val, a);
    }
    a[id] = con(a[2*id], a[2*id+1]);
}

void solve(){
    ll n, q, i, type, l,  r, s, c;
    cin>>n>>q;
    vector<ll> d(n+1);
    vector<Node> a(4*n + 7);
    for(i=1;i<=n;++i){
        cin>>d[i];
    }
    build(1, 0, n, d, a);
    for(i=0;i<q;++i){
        cin>>type;
        if(type == 1){
            cin>>l>>r>>s>>c;
            auto res2 = get(1, 0, n, 0, r, a);
            if(l == r){
                add(1, 0, n, l, s, a);
            }else{
                add(1, 0, n, l, s, a);
                add(1, 0, n, l+1, r, c, a);
            }
            auto res = get(1, 0, n, 0, r, a);
            if(r < n){
                add(1, 0, n, r+1, res2.sum - res.sum, a);
            }
        }else if(type == 2){
            cin>>l>>r>>s>>c;
            auto res = get(1, 0, n, 0, l-1, a);
            auto res2 = get(1, 0, n, 0, r, a);
            if(l == r){
                Set(1, 0, n, l, s - res.sum, a);
            }else{
                Set(1, 0, n, l, s - res.sum, a);
                Set(1, 0, n, l+1, r, c, a);
            }
            res = get(1, 0, n, 0, r, a);
            if(r < n){
                add(1, 0, n, r+1, res2.sum - res.sum, a);
            }
        }else{
            cin>>l>>r;
            auto res = get(1, 0, n, l+1, r, a);
            cout<<res.res + 1<<endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

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