Submission #795024

#	Time	Username	Problem	Language	Result	Execution time	Memory
795024		PoonYaPat	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	977 ms	45880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll s[1<<19][3][3],c[200005],lz[1<<19];
int n,q;

void merge(int a, int b, int res) {
    for (int i=0; i<3; ++i) {
        for (int j=0; j<3; ++j) {
            s[res][i][j]=-1e15;
            for (int k=0; k<3; ++k) s[res][i][j]=max(s[res][i][j],s[a][i][k]+s[b][2-k][j]);

            if (i!=1) s[res][i][j]=max(s[res][i][j],s[b][i][j]);
            if (j!=1) s[res][i][j]=max(s[res][i][j],s[a][i][j]);
        }
    }
}

void push(int l, int r, int idx) {
    if (lz[idx]==-1e16) return;
    if (l!=r) {
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j) {
                if (i==0) s[idx][i][j]-=lz[idx];
                if (i==2) s[idx][i][j]+=lz[idx];
                if (j==0) s[idx][i][j]-=lz[idx];
                if (j==2) s[idx][i][j]+=lz[idx];
            }
        }

        if (lz[2*idx]==-1e16) lz[2*idx]=lz[idx];
        else lz[2*idx]+=lz[idx];

        if (lz[2*idx+1]==-1e16) lz[2*idx+1]=lz[idx];
        else lz[2*idx+1]+=lz[idx];

        lz[idx]=-1e16;

    } else {
        c[l]+=lz[idx];

        s[idx][0][0]=-1e15;
        s[idx][0][1]=-c[l];
        s[idx][0][2]=-1e15;
        s[idx][1][0]=-c[l];
        s[idx][1][1]=0;
        s[idx][1][2]=c[l];
        s[idx][2][0]=-1e15;
        s[idx][2][1]=c[l];
        s[idx][2][2]=-1e15;

        lz[idx]=-1e16;
    }
}

void build(int l, int r, int idx) {
    if (l==r) {
        push(l,r,idx);
    } else {
        int mid=(l+r)/2;
        build(l,mid,2*idx);
        build(mid+1,r,2*idx+1);
        merge(2*idx,2*idx+1,idx);
    }
}

void update(int l, int r, int idx, int x, int y, ll val) {
    push(l,r,idx);
    if (x>r || y<l) return;

    if (x<=l && r<=y) {
        lz[idx]=val;
        push(l,r,idx);
    } else {
        int mid=(l+r)/2;
        update(l,mid,2*idx,x,y,val);
        update(mid+1,r,2*idx+1,x,y,val);
        merge(2*idx,2*idx+1,idx);
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i=0; i<(1<<19); ++i) for (int j=0; j<3; ++j) for (int k=0; k<3; ++k) s[i][j][k]=-1e15;
    for (int i=0; i<(1<<19); ++i) lz[i]=-1e16;

    cin>>n>>q;
    for (int i=1; i<=n; ++i) {
        int x; cin>>x;
        update(1,n,1,i,i,x);
    }

    while (q--) {
        int l,r; ll val;
        cin>>l>>r>>val;
        update(1,n,1,l,r,val);
        cout<<s[1][1][1]<<"\n";
    }
}

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