Submission #691972

#TimeUsernameProblemLanguageResultExecution timeMemory
691972powerleo101Sjeckanje (COCI21_sjeckanje)C++14
110 / 110
500 ms27924 KiB
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <string> #define gi get_int() #define int long long const int MAXN = 1e6; int get_int() { int x = 0, y = 1; char ch = getchar(); while (!isdigit(ch) && ch != '-') ch = getchar(); if (ch == '-') y = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * y; } int tree[MAXN][2][2], num[MAXN], n; void push(int now, int mid) { if (num[mid - 1] * num[mid] >= 0) { tree[now][0][0] = std::max(tree[now << 1][0][0] + tree[now << 1 | 1][0][0], tree[now << 1][0][1] + tree[now << 1 | 1][0][0]); tree[now][1][0] = std::max(tree[now << 1][1][0] + tree[now << 1 | 1][0][0], tree[now << 1][1][1] + tree[now << 1 | 1][0][0]); tree[now][0][1] = std::max(tree[now << 1][0][0] + tree[now << 1 | 1][0][1], tree[now << 1][0][1] + tree[now << 1 | 1][0][1]); tree[now][1][1] = std::max(tree[now << 1][1][0] + tree[now << 1 | 1][0][1], tree[now << 1][1][1] + tree[now << 1 | 1][0][1]); } else { tree[now][0][0] = std::max(tree[now << 1][0][1] + tree[now << 1 | 1][0][0], tree[now << 1][0][0] + tree[now << 1 | 1][1][0]); tree[now][1][0] = std::max(tree[now << 1][1][1] + tree[now << 1 | 1][0][0], tree[now << 1][1][0] + tree[now << 1 | 1][1][0]); tree[now][0][1] = std::max(tree[now << 1][0][1] + tree[now << 1 | 1][0][1], tree[now << 1][0][0] + tree[now << 1 | 1][1][1]); tree[now][1][1] = std::max(tree[now << 1][1][1] + tree[now << 1 | 1][0][1], tree[now << 1][1][0] + tree[now << 1 | 1][1][1]); } } int ABS(int u) { return u < 0 ? -u : u; } void build(int now = 1, int lrange = 0, int rrange = n) { if (lrange == rrange - 1) { tree[now][0][0] = ABS(num[lrange]); return ; } int mid = (lrange + rrange) / 2; build(now << 1, lrange, mid); build(now << 1 | 1, mid, rrange); push(now, mid); } void update(int p, int value, int now = 1, int lrange = 0, int rrange = n) { if (p < lrange || p >= rrange) return ; if (lrange == rrange - 1) { tree[now][0][0] = ABS(num[lrange]); return ; } int mid = (lrange + rrange) / 2; update(p, value, now << 1, lrange, mid); update(p, value, now << 1 | 1, mid, rrange); push(now, mid); //std::cout << lrange << ' ' << rrange << ' ' << tree[now][0][0] << std::endl; } signed main() { #ifdef LOCAL_PROJECT freopen("code.in", "r", stdin); freopen("code.out", "w", stdout); #endif n = gi; int Q = gi; for (int i = 0; i < n; i++) num[i] = gi; for (int i = n - 1; i > 0; i--) num[i] = num[i] - num[i - 1]; num[0] = 0; build(); while (Q--) { int l = gi - 1, r = gi, value = gi; num[l] += value; num[r] -= value; update(l, value); update(r, -value); std::cout << tree[1][1][0] << std::endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...