Submission #513132

#	Time	Username	Problem	Language	Result	Execution time	Memory
513132		Bill_00	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	332 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 200005
#define INF 1000000000
#define MOD 998244353
using namespace std;
ll m[4 * N], lazy[8 * N];
ll n, q;
ll a[N], b[N];
struct block{
	ll L, R, sum;
};

block node[4 * N];
void push(ll id){
	m[id] += lazy[id];
	lazy[id * 2] += lazy[id];
	lazy[id * 2 + 1] += lazy[id];
	lazy[id] = 0;
}
void lol(ll id, ll l, ll r){
	if(l == r){
		m[id] = a[l];
		return;
	}
	ll mm = l + r >> 1;
	lol(id * 2, l, mm);
	lol(id * 2 + 1, mm + 1, r);
	m[id] = max(m[id * 2], m[id * 2 + 1]);
}
void update(ll id, ll l, ll r, ll L, ll R, ll val){
	push(id);
	if(r < L || R < l) return;
	if(L <= l && r <= R){
		m[id] += val;
		lazy[id * 2] += val;
		lazy[id * 2 + 1] += val;
		return;
	}
	int mm = l + r >> 1;
	update(id * 2, l, mm, L, R, val);
	update(id * 2 + 1, mm + 1, r, L, R, val);
	m[id] = max(m[id * 2], m[id * 2 + 1]);
}
ll query(ll id, ll l, ll r, ll pos){
	push(id);
	if(l == r){
		return m[id];
	}
	int mm = l + r >> 1;
	if(pos <= mm) return query(id * 2, l, mm, pos);
	else return query(id * 2 + 1, mm + 1, r, pos);
}
void build(ll id, ll l, ll r){
	if(l > r) return;
	if(l == r){
		if(b[l] == 0){
			node[id].L = -1;
			node[id].R = -1;
		}
		else{
			node[id].L = l;
			node[id].R = r;
		}
		node[id].sum = 0;
		return;
	}	
	ll m = l + r >> 1;
	build(id * 2, l, m);
	build(id * 2 + 1, m + 1, r);
	if(node[id * 2].R == -1 && node[id * 2 + 1].L == -1){
		node[id].L = -1;
		node[id].R = -1;
		node[id].sum = 0;
	}
	else{
		if(node[id * 2].R == -1){
			node[id].L = node[id * 2 + 1].L;
			node[id].R = node[id * 2 + 1].R;
			node[id].sum = node[id * 2 + 1].sum;
		}
		else{
			if(node[id * 2 + 1].L == -1){
				node[id].L = node[id * 2].L;
				node[id].R = node[id * 2].R;
				node[id].sum = node[id * 2].sum;
			}
			else{
				node[id].sum = node[id * 2].sum + node[id * 2 + 1].sum;
				node[id].L = node[id * 2].L;
				node[id].R = node[id * 2 + 1].R;
				bool flag = 0;
				if(b[m] == 0 || b[m + 1] == 0) flag = 1;
				ll k = query(1, 1, n, node[id * 2].R);
				if(b[node[id * 2].R] > 0 && b[node[id * 2 + 1].L] < 0){
					node[id].sum += (2 * k - (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
				}
				if(b[node[id * 2].R] < 0 && b[node[id * 2 + 1].L] > 0){
					node[id].sum -= (2 * k + (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
				}
			}
		}
	}
}
void prob(ll id, ll l, ll r, ll pos){
	if(l > r) return;
	if(l == r){
		if(b[l] == 0){
			node[id].L = -1;
			node[id].R = -1;
		}
		else{
			node[id].L = l;
			node[id].R = r;
		}
		node[id].sum = 0;
		return;
	}
	ll m = l + r >> 1;
	if(m >= pos) prob(id * 2, l, m, pos);
	else prob(id * 2 + 1, m + 1, r, pos);
	if(node[id * 2].R == -1 && node[id * 2 + 1].L == -1){
		node[id].L = -1;
		node[id].R = -1;
		node[id].sum = 0;
	}
	else{
		if(node[id * 2].R == -1){
			node[id].L = node[id * 2 + 1].L;
			node[id].R = node[id * 2 + 1].R;
			node[id].sum = node[id * 2 + 1].sum;
		}
		else{
			if(node[id * 2 + 1].L == -1){
				node[id].L = node[id * 2].L;
				node[id].R = node[id * 2].R;
				node[id].sum = node[id * 2].sum;
			}
			else{
				node[id].sum = node[id * 2].sum + node[id * 2 + 1].sum;
				node[id].L = node[id * 2].L;
				node[id].R = node[id * 2 + 1].R;
				bool flag = 0;
				if(b[m] == 0 || b[m + 1] == 0) flag = 1;
				ll k = query(1, 1, n, node[id * 2].R);
				if(b[node[id * 2].R] > 0 && b[node[id * 2 + 1].L] < 0){
					node[id].sum += (2 * k - (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
				}
				if(b[node[id * 2].R] < 0 && b[node[id * 2 + 1].L] > 0){
					node[id].sum -= (2 * k + (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
				}
			}
		}
	}
}
int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(i > 1) b[i] = a[i] - a[i - 1];
	}
	lol(1, 1, n);	
	build(1, 2, n);
	while(q--){
		int l, r, x;
		cin >> l >> r >> x;
		update(1, 1, n, l, r, x);
		b[l] += x;
		prob(1, 2, n, l);
		b[r + 1] -= x;
		prob(1, 2, n, r + 1);
		ll ans = node[1].sum;
		x = node[1].L;
		ll y = node[1].R;
		if(x == -1){
			cout << 0 << '\n';
		}
		else{
			if(b[x] < 0){
				ll p = query(1, 1, n, x);
				ans += (p - b[x]);
			}
			else{
				ll p = query(1, 1, n, x);
				ans -= (p - b[x]);
			}
			if(b[y] < 0){
				ll p = query(1, 1, n, y);
				ans -= p;
			}
			else{
				ll p = query(1, 1, n, y);
				ans += p;
			}
			cout << ans << '\n';
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'void lol(long long int, long long int, long long int)':
Main.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  ll mm = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int mm = l + r >> 1;
      |           ~~^~~
Main.cpp: In function 'long long int query(long long int, long long int, long long int, long long int)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mm = l + r >> 1;
      |           ~~^~~
Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  ll m = l + r >> 1;
      |         ~~^~~
Main.cpp: In function 'void prob(long long int, long long int, long long int, long long int)':
Main.cpp:122:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |  ll m = l + r >> 1;
      |         ~~^~~

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