제출 #873917

#제출 시각아이디문제언어결과실행 시간메모리
873917noiaintSjeckanje (COCI21_sjeckanje)C++17
110 / 110
624 ms67580 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define file "sjeckanje" #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1LL << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = (int)1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int oo = 1e9; const long long ooo = 1e18; template<class X, class Y> bool mini(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maxi(X &a, Y b) { return a < b ? (a = b, true) : false; } void add(int &a, int b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int n, q; int a[N]; namespace sub_n2 { int f[N][2]; void solve() { while (q--) { int l, r, c; cin >> l >> r >> c; for (int i = l; i <= r; ++i) a[i] += c; for (int i = 0; i <= n; ++i) for (int j = 0; j < 2; ++j) f[i][j] = -ooo; f[1][0] = f[1][1] = 0; for (int i = 1; i < n; ++i) for (int j = 0; j < 2; ++j) { if (f[i][j] == -ooo) continue; if (j == 0) { if (a[i] < a[i + 1]) maxi(f[i + 1][0], f[i][j] + a[i + 1] - a[i]); } if (j == 1) { if (a[i] > a[i + 1]) maxi(f[i + 1][1], f[i][j] + a[i] - a[i + 1]); } maxi(f[i + 1][0], f[i][j]); maxi(f[i + 1][1], f[i][j]); } cout << max(f[n][0], f[n][1]) << '\n'; } } } struct node { int l, r; int f[2][2]; node() { for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) f[i][j] = -ooo; } int get() { return max({f[0][0], f[0][1], f[1][0], f[1][1]}); } }; node t[N]; int lazy[N]; node unite(const node &x, const node &y) { node res; res.l = x.l, res.r = y.r; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) for (int l = 0; l < 2; ++l) if (x.f[i][j] != -ooo && y.f[k][l] != -ooo) { int val = x.f[i][j] + y.f[k][l]; if (j == k) { if (j == 0) { if (x.r < y.l) val += y.l - x.r; } else { if (x.r > y.l) val += x.r - y.l; } } maxi(res.f[i][l], val); } return res; } void build(int i, int L, int R) { if (L == R) { t[i].l = t[i].r = a[L]; t[i].f[0][0] = t[i].f[1][1] = 0; return; } int M = (L + R) >> 1; build(i << 1, L, M); build(i << 1 | 1, M + 1, R); t[i] = unite(t[i << 1], t[i << 1 | 1]); } void down(int i) { for (int j = i * 2; j <= i * 2 + 1; ++j) { t[j].l += lazy[i]; t[j].r += lazy[i]; lazy[j] += lazy[i]; } lazy[i] = 0; } void update(int i, int L, int R, int l, int r, int c) { if (r < L || l > R) return; if (l <= L && R <= r) { t[i].l += c; t[i].r += c; lazy[i] += c; return; } down(i); int M = (L + R) >> 1; update(i << 1, L, M, l, r, c); update(i << 1 | 1, M + 1, R, l, r, c); t[i] = unite(t[i << 1], t[i << 1 | 1]); } void update(int l, int r, int c) { update(1, 1, n, l, r, c); } signed main() { ios::sync_with_stdio(false); cin.tie(0); // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; build(1, 1, n); while (q--) { int l, r, c; cin >> l >> r >> c; update(l, r, c); cout << t[1].get() << '\n'; } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...