oj.uz

Submission #494329

# Submission time Handle Problem Language Result Execution time Memory
494329 2021-12-15T06:41:48 Z 8e7 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 439 ms 29556 KB 
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <chrono>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define ld long double
#define maxn 200005
#define mod 998244353
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll a[maxn], d[maxn];
struct segtree{
	ll seg[4 * maxn][4];
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		bool con = (d[m-1] >= 0) ^ (d[m] >= 0);
		for (int i = 0;i < 4;i++) seg[cur][i] = 0;
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < 4;j++) {
				if (con && (i & 2) && (j&1)) continue;
				seg[cur][(i&1) + (j&2)] = max(seg[cur][(i&1)+(j&2)], seg[cur*2][i] + seg[cur*2+1][j]);
			}
		}	
	}
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur][0] = 0;
			seg[cur][3] = abs(d[l]);
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur * 2 + 1, m, r);
		pull(cur, l, r);
	}
	void modify(int cur, int l, int r, int ind) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur][0] = 0, seg[cur][3] = abs(d[l]);
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind);
		else modify(cur*2+1, m, r, ind);
		pull(cur, l, r);
	}
	ll getval() {
		return *max_element(seg[1], seg[1] + 4);	
	}
} seg;
int main() {
	io
	int n, q;
	cin >> n >> q;
	for (int i = 0;i < n;i++) cin >> a[i];	
	for (int i = 0;i < n - 1;i++) d[i] = a[i+1] - a[i];	
	seg.init(1, 0, n - 1);
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l--, r--;
		d[l-1] += x;d[r] -= x;
		seg.modify(1, 0, n - 1, l - 1);
		seg.modify(1, 0, n - 1, r);
		cout << seg.getval() << "\n";
	}
}
/*

4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 4 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 4 ms 720 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 720 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 4 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 4 ms 720 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 439 ms 29024 KB Output is correct
14 Correct 412 ms 29004 KB Output is correct
15 Correct 387 ms 29000 KB Output is correct
16 Correct 404 ms 28828 KB Output is correct
17 Correct 394 ms 28836 KB Output is correct
18 Correct 379 ms 29556 KB Output is correct