Submission #1098635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098635		flyingkite	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	586 ms	74320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e16;
const ll mod = 1e9 + 7;
const ll block = 450;
ll a[N], dp[N][3]; // 0 la da co +, 1 la da co -, 2 la da xog
ll n,q;
struct ccjv{ll d[3][3];};
struct segment_tree{
    ll n;
    vector<ccjv>st;
    vector<ll>lz;
    ccjv base;
    void init(ll _n){
        n = _n;
        st.resize(4 * n + 10);
        lz.resize(4 * n + 10);
        for(int i = 0; i <= 2;i++){
            for(int j = 0; j <= 2;j++) base.d[i][j] = -inf;
        }
        base.d[2][2] = 0;
        build(1,1,n);
    }
    ccjv merge(const ccjv &a, const ccjv &b){
        ccjv res;
        for(int i = 0; i <= 2;i++){
            for(int j = 0; j <= 2;j++){
                res.d[i][j] = max({a.d[i][j], b.d[i][j], a.d[i][0] + b.d[1][j], a.d[i][1] + b.d[0][j], a.d[i][2] + b.d[2][j]});
            }
        }
        return res;
    }
    void build(ll id, ll l, ll r){
        if(l == r){
            st[id].d[0][2] = st[id].d[2][0] = a[l];
            st[id].d[1][2] = st[id].d[2][1] = -a[l];
            st[id].d[2][2] = 0;
            st[id].d[0][0] = st[id].d[1][1] = st[id].d[1][0] = st[id].d[0][1] = -inf;
            return;
        }
        ll mid = (l + r) / 2;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        st[id] = merge(st[2 * id], st[2 * id + 1]);
    }
    void down(ll id, ll l, ll r){
        if(!lz[id]) return;
        st[id].d[2][0] += lz[id], st[id].d[0][2] += lz[id];
        st[id].d[1][2] -= lz[id], st[id].d[2][1] -= lz[id];
        st[id].d[0][0] += lz[id] * 2;
        st[id].d[1][1] -= lz[id] * 2;
        if(l != r){
            lz[2 * id] += lz[id];
            lz[2 * id + 1] += lz[id];
        }
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] += val;
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = merge(st[2 * id], st[2 * id + 1]);
    }
    ccjv get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return base;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return merge(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    
};
void sub_trau(){
    dp[0][0] = -1e16, dp[0][1] = -1e16, dp[0][2] = 0;
    while(q--){
        ll l,r,x; cin >> l >> r >> x;
        for(int i = l; i <= r;i++) a[i] += x;
        for(int i = 1; i <= n;i++) dp[i][0] = dp[i][1] = dp[i][2] = -1e16;
        for(int i = 1; i <= n;i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][2] + a[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][2] - a[i]);
            dp[i][2] = max({dp[i-1][2], dp[i-1][0] - a[i], dp[i-1][1] + a[i]});
        }
        cout << dp[n][2] << '\n';
    }
}
void sub_full(){
    segment_tree st;
    st.init(n);
    while(q--){
        ll l,r,x; cin >> l >> r >> x;
        st.update(1,1,n,l,r,x);
        cout << st.get(1,1,n,1,n).d[2][2] << '\n';
    }
}
void to_thic_cau(){
    cin >> n >> q;
    for(int i = 1; i <= n;i++) cin >> a[i];
    if(n <= 1000 && q <= 1000) sub_trau();
    else sub_full();
}   
 
signed main(){
    //freopen("DIVISION.inp", "r", stdin);
    //freopen("DIVISION.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55