Submission #1011647

#TimeUsernameProblemLanguageResultExecution timeMemory
1011647Yang8onSjeckanje (COCI21_sjeckanje)C++14
0 / 110
1 ms2392 KiB
#include <bits/stdc++.h> #define Y8o "Sjeckanje" #define maxn (int) 2e5 + 5 #define ll long long #define pii pair<int, int> #define gb(i, j) ((i >> j) & 1) //#define f first //#define s second using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll GetRandom(ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rng); } void iof() { if(fopen(Y8o".inp", "r")) { freopen(Y8o".inp", "r", stdin); // freopen(Y8o".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); } void ctime() { cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; } int n, Q; ll a[maxn], d[maxn]; struct dl { ll op_op, op_cl, cl_op, cl_cl; } st[4 * maxn]; dl change(ll val, dl best = {0, 0, 0, 0}) { best = {val, 0, 0, 0}; return best; } dl cb(dl x, dl y, int mid, dl best = {0, 0, 0, 0}) { best.op_op = max(x.op_op + y.cl_op, x.op_cl + y.op_op); best.op_cl = max(x.op_op + y.cl_cl, x.op_cl + y.op_cl); best.cl_op = max(x.cl_op + y.cl_op, x.cl_cl + y.op_op); best.cl_cl = max(x.cl_op + y.cl_cl, x.cl_cl + y.op_cl); if((d[mid - 1] < 0 && d[mid] < 0) || (d[mid - 1] > 0 && d[mid] > 0)) { best.op_op = max(x.op_cl, x.op_op) + max(y.op_op, y.cl_op); best.op_cl = max(x.op_cl, x.op_op) + max(y.op_cl, y.cl_cl); best.cl_op = max(x.cl_op, x.cl_cl) + max(y.op_op, y.cl_op); best.cl_cl = max(x.cl_op, x.cl_cl) + max(y.op_cl, y.cl_cl); } return best; } void build(int id = 1, int l = 1, int r = n - 1) { if(l == r) { st[id] = change(abs(d[l])); return; } int mid = (l + r) >> 1; build(id * 2, l, mid), build(id * 2 + 1, mid + 1, r); st[id] = cb(st[id * 2], st[id * 2 + 1], mid); } void update(int i, int id = 1, int l = 1, int r = n - 1) { if(i < l || r < i) return ; if(l == r) { st[id] = change(abs(d[i])); return; } int mid = (l + r) >> 1; update(i, id * 2, l, mid), update(i, id * 2 + 1, mid + 1, r); st[id] = cb(st[id * 2], st[id * 2 + 1], mid); } ll ans() { return max({ st[1].op_op, st[1].op_cl, st[1].cl_op, st[1].cl_cl }); } void solve() { cin >> n >> Q; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i < n; i ++) d[i] = a[i + 1] - a[i]; build(); for(int i = 1; i <= Q; i ++) { int u, v; ll val; cin >> u >> v >> val; d[u - 1] += val, d[v] -= val; update(u - 1), update(v); cout << ans() << '\n'; } } int main() { iof(); int nTest = 1; // cin >> nTest; while(nTest --) { solve(); } ctime(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void iof()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...