oj.uz

Submission #541241

# Submission time Handle Problem Language Result Execution time Memory
541241 2022-03-22T20:07:57 Z Olympia Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 688 ms 39568 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;
		if (l^r)
			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 12 ms 29012 KB Output is correct
2 Correct 12 ms 29012 KB Output is correct
3 Correct 13 ms 29064 KB Output is correct
4 Correct 13 ms 29012 KB Output is correct
5 Correct 13 ms 29012 KB Output is correct
6 Correct 14 ms 29000 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29012 KB Output is correct
2 Correct 12 ms 29012 KB Output is correct
3 Correct 13 ms 29064 KB Output is correct
4 Correct 13 ms 29012 KB Output is correct
5 Correct 13 ms 29012 KB Output is correct
6 Correct 14 ms 29000 KB Output is correct
7 Correct 20 ms 29140 KB Output is correct
8 Correct 18 ms 29140 KB Output is correct
9 Correct 19 ms 29180 KB Output is correct
10 Correct 18 ms 29168 KB Output is correct
11 Correct 18 ms 29140 KB Output is correct
12 Correct 17 ms 29084 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29012 KB Output is correct
2 Correct 12 ms 29012 KB Output is correct
3 Correct 13 ms 29064 KB Output is correct
4 Correct 13 ms 29012 KB Output is correct
5 Correct 13 ms 29012 KB Output is correct
6 Correct 14 ms 29000 KB Output is correct
7 Correct 20 ms 29140 KB Output is correct
8 Correct 18 ms 29140 KB Output is correct
9 Correct 19 ms 29180 KB Output is correct
10 Correct 18 ms 29168 KB Output is correct
11 Correct 18 ms 29140 KB Output is correct
12 Correct 17 ms 29084 KB Output is correct
13 Correct 620 ms 38984 KB Output is correct
14 Correct 632 ms 38860 KB Output is correct
15 Correct 618 ms 38860 KB Output is correct
16 Correct 688 ms 38824 KB Output is correct
17 Correct 633 ms 38780 KB Output is correct
18 Correct 570 ms 39568 KB Output is correct