Submission #1006717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006717		doducanh	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	453 ms	50772 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int maxn=2e5+7;
int a[maxn];
int d[maxn];
int n,q;
struct segtree {
    struct info{
        int border[2];
        int dp[2][2];
    };
    vector<info> t;
	int n;
    segtree(){}
	segtree(int n) : n(n),t(4 * n){}
	info combine(int x){
	    info ret;
	    info le=t[x*2];
	    info ri=t[x*2+1];
	    ret.border[0]=le.border[0];
	    ret.border[1]=ri.border[1];
	    ret.dp[0][0]=ret.dp[1][0]=ret.dp[0][1]=ret.dp[1][1]=0;
	    for(int l=0;l<2;l++){
            for(int m=0;m<2;m++){
                for(int o=0;o<2;o++){
                    for(int r=0;r<2;r++){
                        if(m&&o){
                            if((le.border[1]<0)==(ri.border[0]<0))
                            ret.dp[l][r]=max(ret.dp[l][r],le.dp[l][m]+ri.dp[o][r]);
                        }
                        else{
                            ret.dp[l][r]=max(ret.dp[l][r],le.dp[l][m]+ri.dp[o][r]);
                        }
                    }
                }
            }
	    }
	    return ret;
	}
	void build()
	{
	    build(1,1,n-1);
	}
	void build(int id,int l,int r){
	    if(l==r){
            t[id].border[0]=d[l];
            t[id].border[1]=d[l];
            t[id].dp[0][1]=t[id].dp[1][0]=t[id].dp[0][0]=0;
            t[id].dp[1][1]=abs(d[l]);
            return;
	    }
	    int m=(l+r)/2;
	    build(id*2,l,m);
	    build(id*2+1,m+1,r);
	    t[id]=combine(id);
	}
	void upd(int pos,int val){
	    upd(1,1,n-1,pos,val);
	}
	void upd(int id,int l,int r,int pos,int val){
	    if(l==r){
            t[id].border[0]+=val;
            t[id].border[1]+=val;
            t[id].dp[1][1]=abs(t[id].border[0]);
            return;
	    }
	    int m=(l+r)/2;
	    if(pos<=m)upd(id*2,l,m,pos,val);
	    else upd(id*2+1,m+1,r,pos,val);
	    t[id]=combine(id);
	}
	int qry()
	{
	    return t[1].dp[1][1];
	}
};
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)d[i]=a[i+1]-a[i];
    segtree t(n);
    t.build();
//    cout<<t.qry()<<"\n";
    while(q--){
        int l,r,x;
        cin>>l>>r>>x;
        if(l-1>=1)t.upd(l-1,x);
        if(r<=n-1)t.upd(r,-x);
        cout<<t.qry()<<"\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'segtree::segtree(long long int)':
Main.cpp:15:6: warning: 'segtree::n' will be initialized after [-Wreorder]
   15 |  int n;
      |      ^
Main.cpp:14:18: warning:   'std::vector<segtree::info> segtree::t' [-Wreorder]
   14 |     vector<info> t;
      |                  ^
Main.cpp:17:2: warning:   when initialized here [-Wreorder]
   17 |  segtree(int n) : n(n),t(4 * n){}
      |  ^~~~~~~
Main.cpp: At global scope:
Main.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main()
      | ^~~~

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