oj.uz

Submission #960258

# Submission time Handle Problem Language Result Execution time Memory
960258 2024-04-10T03:59:17 Z ono_de206 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 821 ms 39096 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
// typedef pair<int, int> P;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}

template<typename T, typename U>
	istream & operator >> (istream &in, pair<T, U> &c) {
	in >> c.first;
	in >> c.second;
	return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181;// D = 1523, N = 2500;
const long long inf = 2e18 + 10;
int d[mxn * 4][2][2], b[mxn * 4][2], D[mxn];

void up(int i, int x, int y) {
	b[i][0] = b[x][0];
	b[i][1] = b[y][1];
	for(int l = 0; l < 2; l++) {
		for(int r = 0; r < 2; r++) {
			d[i][l][r] = 0;
		}
	}
	for(int l = 0; l < 2; l++) {
		for(int r = 0; r < 2; r++) {
			for(int rr = 0; rr < 2; rr++) {
				for(int ll = 0; ll < 2; ll++) {
					if(ll & rr) {
						if((b[x][1] >= 0 && b[y][0] >= 0) || (b[x][1] <= 0 && b[y][0] <= 0)) {
							mxx(d[i][l][r], d[x][l][rr] + d[y][ll][r]);
						}
					} else {
						mxx(d[i][l][r], d[x][l][rr] + d[y][ll][r]);
					}
				}
			}
		}
	}
}

void build(int l, int r, int i) {
	if(l == r) {
		b[i][0] = b[i][1] = D[l];
		d[i][1][1] = abs(D[l]);
		return;
	}
	int m = (l + r) / 2;
	build(l, m, i * 2);
	build(m + 1, r, i * 2 + 1);
	up(i, i * 2, i * 2 + 1);
}

void update(int l, int r, int i, int x, int y) {
	if(l == r) {
		D[l] += y;
		b[i][0] = b[i][1] = D[l];
		d[i][1][1] = abs(D[l]);
		return;
	}
	int m = (l + r) / 2;
	if(x <= m) update(l, m, i * 2, x, y);
	else update(m + 1, r, i * 2 + 1, x, y);
	up(i, i * 2, i * 2 + 1);
}

void go() {
	int n, q;
	cin >> n >> q;
	int ls;
	cin >> ls;
	if(n == 1) {
		for(int i = 1; i <= q; i++) {
			cout << 0 << endl;
		}
		return;
	}
	for(int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		D[i] = x - ls;
		ls = x;
	}
	build(2, n, 1);
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		if(l > 1) update(2, n, 1, l, x);
		if(r < n) update(2, n, 1, r + 1, -x);
		cout << d[1][1][1] << endl;
	}
}

signed main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 9 ms 4444 KB Output is correct
8 Correct 9 ms 4620 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Correct 9 ms 4624 KB Output is correct
11 Correct 9 ms 4444 KB Output is correct
12 Correct 9 ms 4444 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 9 ms 4444 KB Output is correct
8 Correct 9 ms 4620 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Correct 9 ms 4624 KB Output is correct
11 Correct 9 ms 4444 KB Output is correct
12 Correct 9 ms 4444 KB Output is correct
13 Correct 821 ms 32324 KB Output is correct
14 Correct 793 ms 38488 KB Output is correct
15 Correct 815 ms 38484 KB Output is correct
16 Correct 812 ms 38436 KB Output is correct
17 Correct 795 ms 38412 KB Output is correct
18 Correct 777 ms 39096 KB Output is correct