oj.uz

Submission #442018

# Submission time Handle Problem Language Result Execution time Memory
442018 2021-07-06T18:24:03 Z penguinhacker Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 873 ms 39484 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]+v.la-u.ra);
		if (u.ra>=v.la)
			smax(r.dp[i1][j2], u.dp[i1][1]+v.dp[1][j2]+u.ra-v.la);
		//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 14 ms 29004 KB Output is correct
2 Correct 14 ms 28960 KB Output is correct
3 Correct 14 ms 29056 KB Output is correct
4 Correct 14 ms 28944 KB Output is correct
5 Correct 14 ms 29012 KB Output is correct
6 Correct 15 ms 28976 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29004 KB Output is correct
2 Correct 14 ms 28960 KB Output is correct
3 Correct 14 ms 29056 KB Output is correct
4 Correct 14 ms 28944 KB Output is correct
5 Correct 14 ms 29012 KB Output is correct
6 Correct 15 ms 28976 KB Output is correct
7 Correct 21 ms 29176 KB Output is correct
8 Correct 21 ms 29192 KB Output is correct
9 Correct 23 ms 29172 KB Output is correct
10 Correct 22 ms 29132 KB Output is correct
11 Correct 20 ms 29296 KB Output is correct
12 Correct 20 ms 29184 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29004 KB Output is correct
2 Correct 14 ms 28960 KB Output is correct
3 Correct 14 ms 29056 KB Output is correct
4 Correct 14 ms 28944 KB Output is correct
5 Correct 14 ms 29012 KB Output is correct
6 Correct 15 ms 28976 KB Output is correct
7 Correct 21 ms 29176 KB Output is correct
8 Correct 21 ms 29192 KB Output is correct
9 Correct 23 ms 29172 KB Output is correct
10 Correct 22 ms 29132 KB Output is correct
11 Correct 20 ms 29296 KB Output is correct
12 Correct 20 ms 29184 KB Output is correct
13 Correct 862 ms 39092 KB Output is correct
14 Correct 844 ms 38956 KB Output is correct
15 Correct 873 ms 38832 KB Output is correct
16 Correct 827 ms 39020 KB Output is correct
17 Correct 813 ms 38728 KB Output is correct
18 Correct 764 ms 39484 KB Output is correct