Submission #673686

#	Time	Username	Problem	Language	Result	Execution time	Memory
673686		KLPP	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1333 ms	52708 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<lld,null_type,less<lld>,rb_tree_tag,tree_order_statistics_node_update> order_set;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const lld INF=1e18;
class ST{
	
	public:
	lld arr[1000000][3][3];
	lld lazy[1000000];
	void propag(int a, int b, int node){
		if(lazy[node]!=0){
			rep(i,0,3){
				rep(j,0,3){
					arr[node][i][j]+=lazy[node]*(i-j);
				}
			}
			if(a!=b){
				lazy[2*node]+=lazy[node];
				lazy[2*node+1]+=lazy[node];
			}
			lazy[node]=0;
		}
	}
	void combine(int a, int b, int node){
		rep(i,0,3){
			rep(j,0,3)arr[node][i][j]=-INF;
		}
		rep(i,0,3){
			rep(j,0,3){
				rep(k,0,3){
					arr[node][i][j]=max(arr[node][i][j],arr[2*node][i][k]+arr[2*node+1][k][j]);
				}
			}
		}
	}
	void init(int a, int b, int node){
		
		if(a==b){
			rep(i,0,3){
				rep(j,0,3)arr[node][i][j]=0;
			}
			arr[node][0][2]=-INF;
			arr[node][2][0]=-INF;
			lazy[node]=0;
			return;
		}
		int mid=(a+b)/2;
		init(a,mid,2*node);
		init(mid+1,b,2*node+1);
		combine(a,b,node);
	}
	void update(int a, int b, int node, int l, int r, lld val){
		propag(a,b,node);
		if(r<a || b<l)return;
		if(l<=a && b<=r){
			lazy[node]+=val;
			propag(a,b,node);
			return;
		}
		int mid=(a+b)/2;
		update(a,mid,2*node,l,r,val);
		update(mid+1,b,2*node+1,l,r,val);
		combine(a,b,node);
	}
	/*lld query(int a,int b, int node, int l, int r){
		if(r<a || b<l)return INF;
		if(l<=a && b<=r)return arr[node];
		int mid=(a+b)/2;
		return min(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
	}*/
	void print(int a, int b, int node){
		cout<<a<<" "<<b<<" "<<lazy[node]<<endl;
		rep(i,0,3){
			rep(j,0,3)cout<<arr[node][i][j]<<" ";
			cout<<endl;
		}cout<<endl;
		if(a==b)return;
		int mid=(a+b)/2;
		print(a,mid,2*node);
		print(mid+1,b,2*node+1);
	}
};
lld arr[1000000];
ST S;

void solve(){
	int n,q;
	cin>>n>>q;
	S.init(0,n-1,1);
	rep(i,0,n)cin>>arr[i],S.update(0,n-1,1,i,i,arr[i]);
	while(q--){
		int l,r;
		lld x;
		cin>>l>>r>>x;
		l--;r--;
		S.update(0,n-1,1,l,r,x);
		S.propag(0,n-1,1);
		cout<<S.arr[1][1][1]<<endl;
		//S.print(0,n-1,1);
	}
}

int main(){
	
	int tt;
	tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}

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