oj.uz

Submission #673686

# Submission time Handle Problem Language Result Execution time Memory
673686 2022-12-21T16:40:23 Z KLPP Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1333 ms 52708 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-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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 14 ms 1112 KB Output is correct
8 Correct 13 ms 1112 KB Output is correct
9 Correct 14 ms 1100 KB Output is correct
10 Correct 13 ms 1108 KB Output is correct
11 Correct 13 ms 1092 KB Output is correct
12 Correct 14 ms 1104 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 14 ms 1112 KB Output is correct
8 Correct 13 ms 1112 KB Output is correct
9 Correct 14 ms 1100 KB Output is correct
10 Correct 13 ms 1108 KB Output is correct
11 Correct 13 ms 1092 KB Output is correct
12 Correct 14 ms 1104 KB Output is correct
13 Correct 1271 ms 52052 KB Output is correct
14 Correct 1218 ms 52140 KB Output is correct
15 Correct 1333 ms 52080 KB Output is correct
16 Correct 1220 ms 51868 KB Output is correct
17 Correct 1276 ms 51880 KB Output is correct
18 Correct 1231 ms 52708 KB Output is correct