Submission #862401

#	Time	Username	Problem	Language	Result	Execution time	Memory
862401		velislavgarkov	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	610 ms	39140 KiB

Main

#include <iostream>
using namespace std;
const int MAXN=2e5+10;
struct Node {
    long long dp[2][2];
    long long lef, ri;
};
Node tree[4*MAXN];
long long a[MAXN], dif[MAXN];
Node combine_node(Node a, Node b) {
    Node ans;
    ans.lef=a.lef; ans.ri=b.ri;
    bool fl;
    if ((a.ri<0 && b.lef<0) || (a.ri>0 && b.lef>0)) fl=true;
    else fl=false;
    for (int i=0;i<2;i++) {
        for (int j=0;j<2;j++) {
            ans.dp[i][j]=max(a.dp[i][0]+max(b.dp[1][j],b.dp[0][j]),a.dp[i][1]+b.dp[0][j]);
            if (fl) ans.dp[i][j]=max(ans.dp[i][j],a.dp[i][1]+b.dp[1][j]);
        }
    }
    return ans;
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node].lef=tree[node].ri=dif[l];
        tree[node].dp[0][0]=0;
        tree[node].dp[0][1]=0;
        tree[node].dp[1][0]=0;
        tree[node].dp[1][1]=abs(dif[l]);
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node]=combine_node(tree[node*2],tree[node*2+1]);
}
void update(int node, int l, int r, int qind) {
    if (qind<l || qind>r) return;
    if (l==r) {
        tree[node].lef=tree[node].ri=dif[l];
        tree[node].dp[0][0]=0;
        tree[node].dp[0][1]=0;
        tree[node].dp[1][0]=0;
        tree[node].dp[1][1]=abs(dif[l]);
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,qind);
    update(node*2+1,mid+1,r,qind);
    tree[node]=combine_node(tree[node*2],tree[node*2+1]);
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<n;i++) {
        dif[i]=a[i+1]-a[i];
    }
    build_tree(1,1,n-1);
    int l, r;
    long long x;
    for (int i=0;i<q;i++) {
        cin >> l >> r >> x;
        if (l>1) {
            dif[l-1]+=x;
            update(1,1,n-1,l-1);
        }
        if (r<n) {
            dif[r]-=x;
            update(1,1,n-1,r);
        }
        long long ans=0;
        for (int j=0;j<2;j++) {
            for (int k=0;k<2;k++) ans=max(ans,tree[1].dp[j][k]);
        }
        cout << ans << endl;
    }
    return 0;
}

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