Submission #1263395

#TimeUsernameProblemLanguageResultExecution timeMemory
1263395CodeLakVNSjeckanje (COCI21_sjeckanje)C++20
110 / 110
656 ms32788 KiB
#include <bits/stdc++.h> using namespace std; #define task "main" #define F first #define S second #define ii pair<int, int> #define il pair<int, long long> #define li pair<long long, int> #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } const int MAX_N = (int)2e5 + 5; const long long INF = (long long)1e18 + 1408; int n, q; int a[MAX_N]; int getSign(long long val) { return (val > 0 ? 1 : (val < 0 ? -1 : 0)); } struct NODE { long long leftVal, rightVal, val; long long dp[2][2]; void update(int delta) { val += delta; dp[0][0] = 0; dp[1][1] = abs(val); dp[0][1] = dp[1][0] = -INF; leftVal = rightVal = val; } NODE operator + (const NODE &other) const { NODE res; res.leftVal = leftVal, res.rightVal = other.rightVal; FOR(i, 0, 1) FOR(j, 0, 1) res.dp[i][j] = -INF; FOR(a, 0, 1) FOR(b, 0, 1) FOR(c, 0, 1) FOR(d, 0, 1) { long long ans = dp[a][b] + other.dp[c][d]; if (b && c && getSign(rightVal) * getSign(other.leftVal) == -1) ans -= min(abs(rightVal), abs(other.leftVal)); maximize(res.dp[a][d], ans); } return res; } }; struct IT { NODE tree[4 * MAX_N]; void update(int id, int l, int r, int pos, int val) { if (l > pos || r < pos) return; if (l == r) { tree[id].update(val); return; } int mid = (l + r) >> 1; update(id << 1, l, mid, pos, val); update(id << 1 | 1, mid + 1, r, pos, val); tree[id] = tree[id << 1] + tree[id << 1 | 1]; } long long get() { return max(max(tree[1].dp[0][0], tree[1].dp[0][1]), max(tree[1].dp[1][0], tree[1].dp[1][1])); } } magic; void solve() { cin >> n >> q; FOR(i, 1, n) cin >> a[i]; FOR(i, 1, n - 1) magic.update(1, 1, n - 1, i, a[i + 1] - a[i]); while (q--) { int l, r, val; cin >> l >> r >> val; if (l > 0) magic.update(1, 1, n - 1, l - 1, val); if (r < n) magic.update(1, 1, n- 1, r, -val); cout << magic.get() << "\n"; } } int32_t main() { if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); bool multitest = 0; int numTest = 1; if (multitest) cin >> numTest; while (numTest--) { solve(); } return 0; } /* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...