oj.uz

Submission #537836

# Submission time Handle Problem Language Result Execution time Memory
537836 2022-03-15T16:27:28 Z Cantfindme Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 638 ms 57028 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/4;
const int mod = 1e9+7;

int n, Q;
int A[maxn];
int diff[maxn];

struct dat {
	int v;
	int dp[2][2];
	int ss, se;
	dat () {}
	dat (int nv) {
		v = abs(nv);
		dp[1][1] = abs(nv);
		dp[0][0] = 0;
		dp[0][1] = -INF;
		dp[1][0] = -INF;
		ss = se = (nv < 0);
	}

	void merge(const dat &a, const dat &b) {
		v = 0;
		for (int i =0;i<2;i++) {
			for (int j = 0; j<2;j++) {
				dp[i][j] = max({a.dp[i][0] + b.dp[0][j], a.dp[i][0] + b.dp[1][j], a.dp[i][1] + b.dp[0][j]});
				if (a.se == b.ss) {
					dp[i][j] = max(dp[i][j], a.dp[i][1] + b.dp[1][j]);
				}
				v = max(v, dp[i][j]);
			}
		}
	
		ss = a.ss;
		se = b.se;
	}
};

struct node {
	int s, m, e;
	dat d;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
			d.merge(l -> d, r -> d);
			// cout << s << " " << e << " " << d.v << "\n";
		} else {
			diff[s] = A[s] - A[s-1];
			d = dat(A[s] - A[s-1]);
		}
	}

	void upd(int x, int nv) {
		if (s == e) {
			d = dat(nv);
		} else {
			if (x > m) r -> upd(x,nv);
			else if (x <= m) l -> upd(x,nv);
			d.merge(l -> d, r -> d);
			// cout << "UPD: " << s << " " << e << " " << d.v << "\n";
		}
	}

	int rmq() {
		return d.v;
	}
} *root;

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n >> Q;
	for (int i =1;i<=n;i++) cin >> A[i];
	A[0] = A[1];

	root = new node(1,n);
	// cout << root -> rmq() << "\n";

	for (int q = 0; q<Q;q++) {
		int l, r, x; cin >> l >> r >> x;
		
		if (l != 1) {
			diff[l] += x;
			root -> upd(l, diff[l]);
		}

		if (r+1 <= n) {
			diff[r + 1] -= x;
			root -> upd(r+1, diff[r+1]);
		}	

		// for (int i =1;i<=n;i++) cout << diff[i] << " ";
		// cout << "\n";
		cout << root -> rmq() << "\n";
	}

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 1116 KB Output is correct
8 Correct 4 ms 1112 KB Output is correct
9 Correct 5 ms 1112 KB Output is correct
10 Correct 5 ms 1112 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 1116 KB Output is correct
8 Correct 4 ms 1112 KB Output is correct
9 Correct 5 ms 1112 KB Output is correct
10 Correct 5 ms 1112 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 617 ms 56440 KB Output is correct
14 Correct 615 ms 56420 KB Output is correct
15 Correct 636 ms 56516 KB Output is correct
16 Correct 638 ms 56228 KB Output is correct
17 Correct 612 ms 56216 KB Output is correct
18 Correct 564 ms 57028 KB Output is correct