Submission #957055

#	Time	Username	Problem	Language	Result	Execution time	Memory
957055		hocln	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	659 ms	37940 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
#define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
// I hate cp
const int N = 2e5 + 15;
ll d[N];
struct item{
	ll pseg,sseg,a[2][2]={{0,0},{0,0}};
};

struct segmtree {
	int size = 1;
	vector<item> values;

	item NEUTRAL_ELEMENT;

	item single(int v) {
		item res;
		res.pseg = res.sseg = v;
		res.a[1][1] = abs(v);
		return res;
	}

	item merge(item a, item b) {
		item res;
		res.pseg = a.pseg;
		res.sseg = b.sseg;
		bool good = (a.sseg > 0) == (b.pseg > 0);
		for(int i = 0;i < 2;i++) {
			for(int j = 0;j < 2;j++) {
				for(int x = 0;x < 2;x++) {
					for(int y = 0;y < 2;y++) {
						if(x != y || good) {
							chmax(res.a[i][j],a.a[i][x]+b.a[y][j]);
						}
					}
				}
			}
		}
		return res;
	}

	void init(int n) {
		size = 1;
		while (size < n) size *= 2;
		values.resize(size * 2);
	}

	void build(vector<int>& v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			if (lx < (int)v.size()) {
				values[x] = single(v[lx]);
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(v, 2 * x + 1, lx, m);
		build(v, 2 * x + 2, m, rx);
		values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
	}

	void build(vector<int>& v) {
		build(v, 0, 0, size);
	}

	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			values[x] = single(v);
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		}
		else set(i, v, 2 * x + 2, m, rx);
		values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}

	item calc(int l, int r, int x, int lx, int rx) {
		if (lx >= r || rx <= l) return NEUTRAL_ELEMENT;
		if (lx >= l && rx <= r) return values[x];
		int m = (lx + rx) / 2;
		item v1 = calc(l, r, 2 * x + 1, lx, m);
		item v2 = calc(l, r, 2 * x + 2, m, rx);
		return merge(v1, v2);
	}

	item calc(int l, int r) {
		return calc(l, r, 0, 0, size);
	}
};

 
inline void solve_test() {
	int n, q;
	cin >> n >> q;
	vector<ll>v(n);
	for(auto& i : v) cin >> i;
	segmtree sg;
	sg.init(n);
	for(int i = 0;i < n-1;i++) d[i]=v[i+1]-v[i];
	for(int i = 0;i < n-1;i++) sg.set(i,d[i]);
	while(q--) {
		ll l, r, x;
		cin >> l >> r >> x;
		if(n == 1) {
			cout << "0\n";
			continue;
		}
		--l;
		--r;
		if(l) d[l-1] += x,sg.set(l-1,d[l-1]);
		// -1 -2 4
		if(r != n - 1) d[r] -= x,sg.set(r,d[r]);
		item seg = sg.calc(0,n-1);
		cout << max(max(seg.a[0][0],seg.a[0][1]),max(seg.a[1][0],seg.a[1][1])) << '\n';
		//for(int i = 0;i < sg.values.size();i++) debug()<<imie(i)imie(sg.values[i].seg)imie(sg.values[i].sseg)imie(sg.values[i].pseg)imie(sg.values[i].ind);
		//for(int i = 0;i < n-1;i++) debug()<<imie(i)imie(d[i]);
	}
}
 
int32_t main()
{
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    //freopen("teamwork.in", "r", stdin);
    //freopen("teamwork.out", "w", stdout);
    //cout << "Case #" << tc << ": " << ans << '\n';
    //cout << fixed << setprecision(7);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
		++tc;
        solve_test();
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55