Submission #1114285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114285		ljtunas	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	613 ms	34952 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

#define name "recipe"

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 2e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}
 
template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

int n, a[MAXN], q, l[MAXN], r[MAXN], x[MAXN];

void init() {
    cin >> n >> q;
    For(i, 1, n) cin >> a[i];
    For(i, 1, q) cin >> l[i] >> r[i] >> x[i];
}

namespace sub1{
	int b[205], dp[205];
	void SOLVE() {
		Rep(i, n) b[i] = a[i];
		For(t, 1, q) {
			dp[0] = 0;
			Rep(i, n) dp[i] = -oo;
			For(i, l[t], r[t]) b[i] += x[t];
			Rep(i, n) {
				int Max = -oo, Min = +oo;
				Ford(j, i, 1) {
					maximize(Max, b[j]);
					minimize(Min, b[j]);
					maximize(dp[i], dp[j - 1] + Max - Min);
				}
			}
			cout << dp[n] << '\n';
		}
	}
}

namespace sub2{
	int b[3005], dp[3005][2], d[3005];

	void SOLVE() {
		Rep(i, n) b[i] = a[i];
		
		For(t, 1, q) {
			For(i, l[t], r[t]) b[i] += x[t];
			reset(d, 0);
			reset(dp, 0);
			For(i, 2, n) {
				d[i] = b[i] - b[i - 1];
			}
			For(i, 1, n) {
				dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
				dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] * (d[i]*d[i-1] >= 0)) + abs(d[i]);
			}
			cout << max(dp[n][0], dp[n][1]) << '\n';
		}
	}
}

namespace sub3{
	int d[MAXN];
	struct DATA{
		int dp[2][2];
	};
	struct SegTree{
		#define left(id)  (id << 1)
		#define right(id) (id << 1 | 1)
		#define mid(l, r) ((l + r) >> 1)
		DATA ST[MAXN * 4];
		void update(int id, int l, int r, int u, int v, int val) {
			if (v < l || r < u || r < l || v < u) return;
			if (l == r) {
				ST[id].dp[1][1] = abs(val);
				return; 
			}
			int mid = mid(l, r);
			update(left(id), l, mid, u, v, val);
			update(right(id), mid + 1, r, u, v, val);
			For(i, 0, 1) For(j, 0, 1) {
				ST[id].dp[i][j] = 0;
				For(a, 0, 1) For(b, 0, 1) {
					if (a == b && a == 1 && d[mid] * d[mid + 1] < 0) continue;
					ST[id].dp[i][j] = max(ST[id].dp[i][j], ST[left(id)].dp[i][a] + ST[right(id)].dp[b][j]);
				}
			}
		}
	} IT;
	void SOLVE() {
		For(i, 2, n) d[i] = a[i] - a[i - 1];
		For(i, 2, n) IT.update(1, 2, n, i, i, d[i]);
		For(t, 1, q) {
			d[l[t]] += x[t];
			d[r[t] + 1] -= x[t];
			IT.update(1, 2, n, l[t], l[t], d[l[t]]);
			IT.update(1, 2, n, r[t] + 1, r[t] + 1, d[r[t] + 1]);
			int ans = -oo;
			maximize(ans, IT.ST[1].dp[0][0]);
			maximize(ans, IT.ST[1].dp[0][1]);
			maximize(ans, IT.ST[1].dp[1][0]);
			maximize(ans, IT.ST[1].dp[1][1]);
			cout << ans << '\n';
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    //_______________________________
    init();
    // sub2::SOLVE();
    // sub1::SOLVE();
    // sub2::SOLVE();
    sub3::SOLVE();
    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

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