Submission #874360

#	Time	Username	Problem	Language	Result	Execution time	Memory
874360		ngjabach	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	661 ms	64056 KiB

Main

// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18+7;
struct ask{
    int x,y;
    ll z;
};
ll arr[N];
int q,n;
vector<ask>queries;
namespace sub1{
    ll a[205],dp[205],minis[205][205],maxis[205][205];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<=n;++i){
                maxis[i][i]=a[i];
                minis[i][i]=a[i];
                for(int j=i+1;j<=n;++j){
                    maxis[i][j]=max(maxis[i][j-1],a[j]);
                    minis[i][j]=min(minis[i][j-1],a[j]);
                }
            }
            dp[0]=0;
            for(int i=1;i<=n;++i){
                dp[i]=-INF;
                for(int j=1;j<=i;++j) dp[i]=max(dp[i],dp[j-1]+maxis[j][i]-minis[j][i]);
            }
            ans.pb(dp[n]);
        }
        return ans;
    }
}
namespace sub2{
    ll a[3005],dp[3005][2],d[3005];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<n;++i) d[i]=a[i]-a[i+1];
            dp[0][0]=0; dp[0][1]=0; d[n]=0;
            for(int i=1;i<n;++i){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1]*(d[i]*d[i-1]>=0))+abs(d[i]);
            }
            ans.pb(max(dp[n-1][0],dp[n-1][1]));
        }
        return ans;
    }
}
namespace sub3{
    ll a[N],d[N],lazy[4*N];
    struct node{
        ll l,r;
        ll F[2][2];
        node(){
            for(int i=0;i<2;++i){
                for(int j=0;j<2;++j){
                    F[i][j]=-INF;
                }
            }
            return;
        }
    }seg[4*N];
    node Combine(node A,node B){
        node C;
        C.l=A.l; C.r=B.r;
        for(int x=0;x<2;++x){
            for(int y=0;y<2;++y){
                for(int u=0;u<2;++u){
                    for(int v=0;v<2;++v){
                        if(A.F[x][y]==-INF or B.F[u][v]==-INF) continue;
                        ll best=A.F[x][y]+B.F[u][v];
                        if(y==u){
                            if(y==0 and A.r<B.l) best+=B.l-A.r;
                            else if(y==1 and A.r>B.l) best+=A.r-B.l;
                        }
                        C.F[x][v]=max(C.F[x][v],best);
                    }
                }
            }
        }
        return C;
    }
    void Build(int x,int L,int R){
        lazy[x]=0;
        if(L==R){
            seg[x].l=seg[x].r=a[L];
            seg[x].F[0][0]=0; seg[x].F[1][1]=0;
            return;
        }
        int mid=(L+R)/2;
        Build(2*x,L,mid);
        Build(2*x+1,mid+1,R);
        seg[x]=Combine(seg[2*x],seg[2*x+1]);
        return;
    }
    void Update_Lazy(int x,int L,int R){
        if(!lazy[x]) return;
        seg[x].l+=lazy[x]; seg[x].r+=lazy[x];
        if(L!=R){
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
        }
        lazy[x]=0;
        return;
    }
    void Update(int x,int L,int R,int lo,int hi,ll val){
        Update_Lazy(x,L,R);
        if(L>hi or R<lo) return;
        else if(L>=lo and R<=hi){
            lazy[x]=val;
            Update_Lazy(x,L,R);
            return;
        }
        int mid=(L+R)/2;
        Update(2*x,L,mid,lo,hi,val);
        Update(2*x+1,mid+1,R,lo,hi,val);
        seg[x]=Combine(seg[2*x],seg[2*x+1]);
        return;
    }
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        Build(1,1,n);
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            Update(1,1,n,x,y,z);
            ll res=-INF;
            for(int i=0;i<2;++i) for(int j=0;j<2;++j) res=max(res,seg[1].F[i][j]);
            ans.pb(res);
        }
        return ans;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("RECIPE.inp","r",stdin);
//    freopen("RECIPE.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=0;i<q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        queries.pb({x,y,z});
    }
    vector<ll>ans;
//    if(n<=200 and q<=200) ans=sub1::solve();
//    else if(n<=3000 and q<=3000) 
    ans=sub3::solve();
    for(ll &tmp:ans) cout<<tmp<<endl;
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

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