Submission #1291929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291929		herominhsteve	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	1836 ms	131832 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "FOOD"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const long long INF = (long long) 1e16 + 15092007;

struct Matrix{
	int n,m;
	vector<vector<long long>> matrix;
	
	Matrix(int N=0,int M=0){
		n = N;
		m = M;
		if (n>0 and m>0){
			matrix.assign(n,vector<long long>(m,0));
		}
	}

	inline void toUnit(){
		for (int i=0;i<n;i++) matrix[i][i] = 0;
	}

	Matrix operator * (const Matrix &other) const{
		Matrix res(n,other.m);
		
		for (int i=0;i<n;i++){
			for (int j=0;j<other.m;j++){
				for (int k=0;k<m;k++){
					long long total = matrix[i][k] + other.matrix[k][j];
					maximize(res.matrix[i][j],total);
				}
			}
		}
		return res;
	}	

    long long getMax() const{
        long long res = 0;
        for (const vector<long long> &v : matrix)
            for (const long long &x : v)
                maximize(res,x);
        return res;
    }
};

int n,q;
vector<long long> a;

void init(){
	cin>>n>>q;
	a.assign(n+1,0);
	for (int i=1;i<=n;i++)
		cin>>a[i];
}

namespace BruteForce{
	void solve(){
		while (q--){
			int l,r;
			long long x;
			cin>>l>>r>>x;
			for (int i=l;i<=r;i++) a[i] += x;
            vector<long long> diff(n+1, 0);
            for (int i = 1; i <= n-1; i++)
                diff[i] = a[i+1] - a[i];

            /*
             * 0: no take
             * 1: take
            */
            vector<vector<long long>> dp(n+2,vector<long long>(2,0));

            dp[n-1][0] = 0;
            dp[n-1][1] = llabs(diff[n-1]);

            for (int i = n-2; i >= 1; i--) {
                dp[i][0] = max(dp[i+1][0], dp[i+1][1]);
                if ((diff[i] > 0 and diff[i+1] > 0) or
                    (diff[i] < 0 and diff[i+1] < 0) or
                    diff[i] == 0 or diff[i+1] == 0) {

                    dp[i][1] = llabs(diff[i]) + max(dp[i+1][0], dp[i+1][1]);

                } else {
                    dp[i][1] = llabs(diff[i]) + dp[i+1][0];
                }
            }

            long long res = max(dp[1][0], dp[1][1]);
			cout<<res<<el;
		}
		exit(0);
	}
};

struct SegmentTree{
	int n;
	vector<Matrix> st;

	SegmentTree(int N): n(N){
		st.assign(4 * n + 4,Matrix(2,2));
	}

	void build(int node,int l,int r,const vector<long long> &a){
		if (l==r){
            st[node] = Matrix(2,2);
            if (a[l] < 0) st[node].matrix[0][0] = -a[l];
            else st[node].matrix[1][1] = a[l];
            return;
		}
        int mid = (l+r)>>1;
        build(2*node,l,mid,a);
        build(2*node+1,mid+1,r,a);
        st[node] = st[2*node] * st[2*node + 1];
	}

    void build(const vector<long long> &a){
        build(1,1,n,a);
    }

	void update(int node,int l,int r,int pos,long long val){
		if (l>r) return;
		if (l==r){
            st[node] = Matrix(2,2);
            if (val < 0) st[node].matrix[0][0] = -val;
            else st[node].matrix[1][1] = val;
			return;
		}
		int mid = (l+r)>>1;
		if (pos <= mid) update(2*node,l,mid,pos,val);
		else update(2*node+1,mid+1,r,pos,val);
        st[node] = st[2*node] * st[2*node + 1];
	}

	void update(int pos,long long val){
		update(1,1,n,pos,val);
	}

    Matrix getMatrix(int node,int l,int r,int wanted_l,int wanted_r){
        if (wanted_r < l or r < wanted_l) return Matrix(2,2);
        if (wanted_l <= l and r <= wanted_r) return st[node];
        int mid = (l+r)>>1;
        return getMatrix(2*node,l,mid,wanted_l,wanted_r) 
                * getMatrix(2*node+1,mid+1,r,wanted_l,wanted_r);
    }

    Matrix getMatrix(int l,int r){
        return getMatrix(1,1,n,l,r);
    }

};

namespace MaxPlusMatrix{
	void solve(){
        vector<long long> diff(n,0);
        for (int i=1;i<n;i++)
            diff[i] = a[i+1] - a[i];
        SegmentTree st(n-1);
        st.build(diff);
        while (q--){
            int l,r;
            long long x;
            cin>>l>>r>>x;
            if (l > 1) {
                int pos = l-1;
                diff[pos] += x;
                st.update(pos, diff[pos]);
            }
            if (r <= n-1) {
                int pos = r;
                diff[pos] -= x;
                st.update(pos, diff[pos]);
            }
            cout<<st.getMatrix(1,n).getMax()<<el;
        }
	}
};

void sol(){
	if (n <= 200 and q <= 200) BruteForce::solve();
	MaxPlusMatrix::solve();
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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