oj.uz

답안 #487800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487800 2021-11-16T16:45:23 Z grt Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 332 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200'000 + 10;
const ll INF = 1e18;
int n, q;
ll val[(1 << 18)];

struct Node {
	ll f[2][2];
	int l, r;
};

Node T[(1 << 19)];
int R;

Node combine(Node &a, Node &b) {
	Node c;
	for(int l : {0,1}) for(int r : {0,1}) c.f[l][r] = 0;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			for(int l1 : {0,1}) {
				for(int r1 : {0,1}) {
					if(l1 + r1 == 2 && (ll)val[a.r] * val[b.r] < 0) continue;
					c.f[l][r] = max(c.f[l][r], a.f[l][l1] + b.f[r1][r]);
				}
			}
		}
	}
	return c;
}

void upd(int a, ll x) {
	a += R;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			if(l != r) T[a].f[l][r] = -INF;
			else if(r) T[a].f[l][r] = abs(x);
			else T[a].f[l][r] = 0;
		}
	}
	while(a > 1) {
		a /= 2;
		T[a] = combine(T[2*a], T[2*a+1]);
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < n; ++i) {
		cin >> val[i];
	}
	for(int i = 0; i < n - 1; ++i) {
		val[i] -= val[i + 1];
	}
	val[n - 1] = 0;
	R = 1;
	while(R < n) R *= 2;
	for(int i = R; i < R * 2; ++i) {
		T[i].l = T[i].r = i - R;
	}
	for(int i = 0; i < R; ++i) {
		upd(i, val[i]);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l-=2;
		if(l >= 0) {
			val[l] -= x;
			upd(l, val[l]);
		}
		r--;
		if(r < n - 1) {
			val[r] += x;
			upd(r, val[r]);
		}
		ll ans = 0;
		for(int a : {0,1}) for(int b : {0,1}) ans = max(ans, T[1].f[a][b]);
		cout << ans << "\n";
	}
	
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -