Submission #1208347

#TimeUsernameProblemLanguageResultExecution timeMemory
1208347vaneaSjeckanje (COCI21_sjeckanje)C++20
0 / 110
1 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e6+10; array<ll, 5> st[mxN]; vector<int> v; ll add[mxN]; array<ll, 5> comb(array<ll, 5> a, array<ll, 5> b, int l, int r) { array<ll, 5> ans = {0, 0, 0, 0, 0}; if(a[2] < b[3]) { ans[0] = a[0] + b[0] + (b[3] - a[2]); ans[1] = b[1]; ans[2] = b[2]; ans[3] = a[3]; ans[4] = a[4]; ll curr = b[4]-a[1]; if(a[0] == a[2]-a[1]) { ans[4] = b[4]; } if(b[0] == b[2]-b[1]) { ans[1] = a[1]; } } else if(b[4] < a[1]) { ans[0] = a[0] + b[0] + (a[1]-b[4]); ans[1] = b[1]; ans[2] = b[2]; ans[3] = a[3]; ans[4] = a[4]; if(a[0] == a[2]-a[1]) { ans[3] = b[3]; } if(b[0] == b[2]-b[1]) { ans[2] = a[2]; } } else { ans[0] = a[0] + b[0]; ans[1] = b[1]; ans[2] = b[2]; ans[3] = a[3]; ans[4] = a[4]; } return ans; } void build(int node, int l, int r) { if(l == r) { st[node] = {0, v[l], v[l], v[l], v[l]}; return ; } int mid = (l+r)/2; build(node*2, l, mid); build(node*2+1, mid+1, r); st[node] = comb(st[node*2], st[node*2+1], l, r); } void push(int node, int l, int r) { if(add[node]) { add[node*2] += add[node]; add[node*2+1] += add[node]; for(int j = 1; j <= 4; j++) { st[node*2][j] += add[node]; st[node*2+1][j] += add[node]; } } add[node] = 0; } void upd(int node, int l, int r, int l1, int r1, ll k) { push(node, l, r); if(l1 <= l && r <= r1) { for(int j = 1; j <= 4; j++) { st[node][j] += k; } add[node] += k; return ; } if(l > r1 || r < l1) return ; int mid = (l+r)/2; upd(node*2, l, mid, l1, r1, k); upd(node*2+1, mid+1, r, l1, r1, k); st[node] = comb(st[node*2], st[node*2+1], l, r); } int main() { //freopen("sjeckanje.in.txt", "r", stdin); ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; v.resize(n); for(int i = 0; i < n; i++) { cin >> v[i]; } build(1, 0, n-1); while(q--) { int l, r; ll k; cin >> l >> r >> k; --l; --r; upd(1, 0, n-1, l, r, k); cout << st[1][0] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...