oj.uz

Submission #541262

# Submission time Handle Problem Language Result Execution time Memory
541262 2022-03-22T20:44:54 Z Olympia Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 67 ms 62444 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
#define for2(i) for (int i=0; i<2; ++i)
 
const int mxN=2e5;
int n, q, a[mxN];
 
void smax(ll& i, ll j) {
	if (j>i)
		i=j;
}
 
struct Node {
	ll la, ra, lz=0, dp[2][2];
	Node() {
		dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=-1e18;
	}
} st[1<<19];
 
Node cmb(Node u, Node v) {
	Node r;
	r.la=u.la;
	r.ra=v.ra;
	for2(i1) for2(j2) {
		for2(j1) for2(i2)
			smax(r.dp[i1][j2], u.dp[i1][j1]+v.dp[i2][j2]);
		if (u.ra<=v.la)
			smax(r.dp[i1][j2], u.dp[i1][0]+v.dp[0][j2]+abs(v.la-u.ra));
      else 
        smax(r.dp[i1][j2], u.dp[i1][1]+v.dp[1][j2]+abs(v.la-u.ra));
		//cout << i1 << " " << j2 << " " << r.dp[i1][j2] << endl;
	}
	return r;
}
 
void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u].la=st[u].ra=a[l];
		st[u].dp[0][0]=st[u].dp[1][1]=0;
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}
 
void psh(int u, int l, int r) {
	if (st[u].lz) {
		st[u].la+=st[u].lz;
		st[u].ra+=st[u].lz;
		st[2*u].lz+=st[u].lz, st[2*u+1].lz+=st[u].lz;
		st[u].lz=0;
	}
}
 
int ql, qr, x;
void upd(int u=1, int l=0, int r=n-1) {
	psh(u, l, r);
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		st[u].lz+=x;
		psh(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	upd(2*u, l, mid);
	upd(2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	bld();
	while(q--) {
		cin >> ql >> qr >> x, --ql, --qr;
		upd();
		cout << max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]}) << "\n";
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28992 KB Output is correct
2 Correct 14 ms 29064 KB Output is correct
3 Correct 13 ms 29052 KB Output is correct
4 Correct 13 ms 28956 KB Output is correct
5 Correct 16 ms 28972 KB Output is correct
6 Correct 13 ms 29064 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28992 KB Output is correct
2 Correct 14 ms 29064 KB Output is correct
3 Correct 13 ms 29052 KB Output is correct
4 Correct 13 ms 28956 KB Output is correct
5 Correct 16 ms 28972 KB Output is correct
6 Correct 13 ms 29064 KB Output is correct
7 Correct 18 ms 29200 KB Output is correct
8 Correct 18 ms 29172 KB Output is correct
9 Correct 18 ms 29196 KB Output is correct
10 Correct 18 ms 29100 KB Output is correct
11 Correct 18 ms 29192 KB Output is correct
12 Correct 18 ms 29228 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28992 KB Output is correct
2 Correct 14 ms 29064 KB Output is correct
3 Correct 13 ms 29052 KB Output is correct
4 Correct 13 ms 28956 KB Output is correct
5 Correct 16 ms 28972 KB Output is correct
6 Correct 13 ms 29064 KB Output is correct
7 Correct 18 ms 29200 KB Output is correct
8 Correct 18 ms 29172 KB Output is correct
9 Correct 18 ms 29196 KB Output is correct
10 Correct 18 ms 29100 KB Output is correct
11 Correct 18 ms 29192 KB Output is correct
12 Correct 18 ms 29228 KB Output is correct
13 Runtime error 67 ms 62444 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -