Submission #1193065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193065		HuyAT	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	320 KiB

Main

#include <bits/stdc++.h>
#define newl '\n'
const int N = 2e5 + 10;
const long long INF = 1e18;

struct Node {
	long long f[3][3],lazy;
	Node() : f(),lazy(0) {
		///assume val equals to zero
		for(int i = 0; i < 2; ++i) {
			for(int j = 0; j < 2; ++j) {
				f[i][j] = -INF;
			}
		}
	}
	Node operator + (const Node &other) const {
		Node ans;
		for(int i = 0;i < 3;++i){
		    for(int j = 0;j < 3;++j){
		        ans.f[i][j] = -INF;
		    }
		}
		bool check = false;
		for(int i = 0; i < 3; ++i) {
			for(int j = 0; j < 3; ++j) {
				for(int k = 0; k < 3; ++k) {
					for(int l = 0; l < 3; ++l) {
						if((j + k == 1) || (j == 2 && k == 2)) {
							ans.f[i][l] = std::max(ans.f[i][l],f[i][j] + other.f[k][l]);
						}
						if(j == 2 && i + k == 1){
						    ans.f[2][l] = std::max(ans.f[2][l],f[i][j] + other.f[k][l]);
						}
						if(k == 2 && l + j == 1){
						    ans.f[i][2] = std::max(ans.f[i][2],f[i][j] + other.f[k][l]);
						}
					}
				}
			}
		}
		return ans;
	}
};
struct SegmentTree {
	int n, lg;
	std::vector<Node> st;
	SegmentTree(int _n) : n(_n), st(n * 4  + 10,Node()) {

	}
	void apply(int id,long long lazy) {
		for(int i = 0; i < 3; ++i) {
			for(int j = 0; j < 3; ++j) {
				st[id].f[i][j] -= (i == 0) * lazy;
				st[id].f[i][j] += (i == 1) * lazy;
				st[id].f[i][j] -= (j == 0) * lazy;
				st[id].f[i][j] += (j == 1) * lazy;
			}
		}
		st[id].lazy += lazy;
	}
	void up(int id) {
		st[id] = st[id << 1] + st[id << 1 | 1];
	}
	void down(int id) {
		apply(id << 1,st[id].lazy);
		apply(id << 1 | 1,st[id].lazy);
		st[id].lazy = 0;
	}
	void update(int l,int r,int u,int v,long long val,int id = 1) {
		if(u <= l && r <= v) {
			apply(id,val);
			return;
		}
		down(id);
		int mid = (l + r) / 2;
		if(v <= mid) {
			update(l,mid,u,v,val,id << 1);
		} else if(u > mid) {
			update(mid + 1,r,u,v,val,id << 1 | 1);
		} else {
			update(l,mid,u,v,val,id << 1);
			update(mid + 1,r,u,v,val,id << 1 | 1);
		}
		up(id);
	}
};
long long a[N + 1],n,q;

void readData() {
	std::cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		std::cin >> a[i];
	}
}
void solve() {
	SegmentTree st(n);
	for(int i = 1; i <= n; ++i) {
		st.update(1,n,i,i,a[i]);
	}
	for(int i = 1;i <= q;++i){
	    int l,r,x;
	    std::cin >> l >> r >> x;
	    st.update(1,n,l,r,x);
	    std::cout << st.st[1].f[2][2] << newl;
	}
}
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	readData();
	solve();
    return 0;
}

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