This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |