Submission #924151

#	Time	Username	Problem	Language	Result	Execution time	Memory
924151		iskhakkutbilim	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int mod = 1e9 + 7;

struct node{
	int mn, mx, lazy, cnt_mn, cnt_mx;
};
node UND =  {mod, -mod, 0, 0, 0};
struct Segtree{
	int n;
	vector<node> t;
	Segtree(int sz){
		n = sz;
		t.resize(n * 4, UND);
	};
	node merge(node A, node B){
		int m1 = A.cnt_mn + B.cnt_mn, m2 = A.cnt_mx + B.cnt_mx;
		if(A.mx > B.mx) m2-= B.cnt_mx;
		if(B.mx > A.mx) m2-= A.cnt_mx;
		
		if(A.mn < B.mn) m1-= B.cnt_mn; 
		if(B.mn < A.mn) m1-= A.cnt_mn;
		
		return {min(A.mn, B.mn), max(A.mx, B.mx),  A.lazy + B.lazy, m1, m2};
	}
	void build(vector<int> &a, int v, int vl, int vr){
		if(vl == vr){
			t[v] = {a[vl], a[vl], 0, 1, 1};
		}else{
			int mid = (vl + vr)>>1;
			build(a, v<<1, vl, mid);
			build(a, v<<1|1, mid+1, vr);
			t[v] = merge(t[v<<1], t[v<<1|1]);
		}
	}
	void push(int v, int vl, int vr){
		if(!t[v].lazy) return;
		t[v].mn+= t[v].lazy;
		t[v].mx+= t[v].lazy;
		if(vl != vr){
			t[v<<1].lazy+= t[v].lazy;
			t[v<<1|1].lazy+= t[v].lazy;
		}
		t[v].lazy = 0;
	}
	
	
	void add(int l, int r, int x, int v, int vl, int vr){
		push(v, vl, vr);
		if(l >  vr or vl > r) return;
		if(l <= vl and r >= vr){
			t[v].lazy+= x;
			push(v, vl, vr);
			return;
		}
		int mid = (vl + vr)>>1;
		add(l, r, x, v<<1, vl, mid);
		add(l, r, x, v<<1|1, mid+1, vr);
		t[v] = merge(t[v<<1], t[v<<1|1]);
	}
	
	
	node get(int l, int r, int v, int vl, int vr){
		push(v, vl, vr);
		if(l > vr or vl > r) return UND;
		if(l <= vl and r >= vr) return t[v];
		int mid = (vl + vr)>>1;
		return merge(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
	}	
};


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	int n, q; cin >> n >> q;
	vector<int> a(n+1);
	for(int i = 1;i <= n; i++){
		cin >> a[i];
	}
	Segtree tree(n+1);
	tree.build(a, 1, 1, n);
	while(q--){
		int l, r, x; cin >> l >> r >> x;
		tree.add(l, r, x, 1, 1, n);
		node res = tree.get(1, n, 1, 1, n);
		int c = min(res.cnt_mx, res.cnt_mn);
		cout << (res.mx * c) - (res.mn * c) << '\n';	
	}
	return 0;
}

Compilation message (stderr)

Main.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main(){
      | ^~~~

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