답안 #673676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673676 2022-12-21T16:20:54 Z KLPP Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
1 ms 320 KB
#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==1)-(i==2)+(j==1)-(j==2));
				}
			}
			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){
					rep(l,0,3){
						if((j+k)%3==0){
							arr[node][i][l]=max(arr[node][i][l],arr[2*node][i][j]+arr[2*node+1][k][l]);
						}
					}
				}
			}
		}
	}
	void init(int a, int b, int node){
		
		if(a==b){
			rep(i,0,3){
				rep(j,0,3)arr[node][i][j]=0;
			}
			rep(i,1,3){
				rep(j,1,3)arr[node][i][j]=-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][0][0]<<"\n";
		//S.print(0,n-1,1);
	}
}

int main(){
	
	int tt;
	tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -