이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
// #define ll long long
#define int long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
template<typename T>
void max_self(T& a, T b) {
if(a < b) {
a = b;
}
}
const int nax = 2e5 + 1;
struct Node {
int ans[2][2] = {0};
int sides[2] = {0};
Node() {}
};
Node tree[4 * nax];
int sgn(int n) {
return n >= 0 ? 1 : -1;
}
Node merge(Node left, Node right) {
Node res;
res.sides[0] = left.sides[0];
res.sides[1] = right.sides[1];
for(int l = 0; l < 2; ++l) {
for(int r = 0; r < 2; ++r) {
for(int ll = 0; ll < 2; ++ll) {
for(int rr = 0; rr < 2; ++rr) {
if(!r || !ll) { // one of the value isn't taken so you can just gather the two parts
max_self(res.ans[l][rr], left.ans[l][r] + right.ans[ll][rr]);
} else if(sgn(left.sides[1]) == sgn(right.sides[0])) { // you can merge here since the sign doesn't change
max_self(res.ans[l][rr], left.ans[l][r] + right.ans[ll][rr]);
}
}
}
}
}
return res;
}
void upd(Node& cur, int v) { // only used in the case of leaf node
cur.sides[0] += v;
cur.sides[1] += v;
assert(cur.sides[1] == cur.sides[0]);
cur.ans[1][1] = abs(cur.sides[0]);
}
void upd(int node, int l, int r, int pos, int v) {
if(r < pos || pos < l) return;
if(l == r) {
upd(tree[node], v);
return;
}
int mid = (l + r) / 2;
upd(node * 2, l, mid, pos, v);
upd(node * 2 + 1, mid + 1, r, pos, v);
tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}
signed main()
{
ios
int n, q; cin >> n >> q;
vector<int> a(n); for(int& x : a) cin >> x;
vector<int> diff(n - 1);
for(int i = 0; i < n - 1; ++i) {
diff[i] = a[i + 1] - a[i];
upd(1, 0, n - 2, i, diff[i]);
}
while(q--) {
int l, r, x; cin >> l >> r >> x; l--, --r;
if(l > 0) {
upd(1, 0, n - 2, l - 1, -x);
}
if(r < n - 1) {
upd(1, 0, n - 2, r, x);
}
int ans = 0;
for(int l = 0; l < 2; ++l) {
for(int r = 0; r < 2; ++r) {
max_self(ans, tree[1].ans[l][r]);
}
}
cout << ans << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |