oj.uz

Submission #868154

# Submission time Handle Problem Language Result Execution time Memory
868154 2023-10-30T13:54:11 Z wakandaaa Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 658 ms 67924 KB 
#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;
}

/*

*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51548 KB Output is correct
2 Correct 7 ms 51728 KB Output is correct
3 Correct 7 ms 51548 KB Output is correct
4 Correct 7 ms 51548 KB Output is correct
5 Correct 7 ms 51548 KB Output is correct
6 Correct 7 ms 51548 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51548 KB Output is correct
2 Correct 7 ms 51728 KB Output is correct
3 Correct 7 ms 51548 KB Output is correct
4 Correct 7 ms 51548 KB Output is correct
5 Correct 7 ms 51548 KB Output is correct
6 Correct 7 ms 51548 KB Output is correct
7 Correct 12 ms 51804 KB Output is correct
8 Correct 13 ms 51804 KB Output is correct
9 Correct 13 ms 51908 KB Output is correct
10 Correct 13 ms 51800 KB Output is correct
11 Correct 12 ms 51800 KB Output is correct
12 Correct 12 ms 51720 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51548 KB Output is correct
2 Correct 7 ms 51728 KB Output is correct
3 Correct 7 ms 51548 KB Output is correct
4 Correct 7 ms 51548 KB Output is correct
5 Correct 7 ms 51548 KB Output is correct
6 Correct 7 ms 51548 KB Output is correct
7 Correct 12 ms 51804 KB Output is correct
8 Correct 13 ms 51804 KB Output is correct
9 Correct 13 ms 51908 KB Output is correct
10 Correct 13 ms 51800 KB Output is correct
11 Correct 12 ms 51800 KB Output is correct
12 Correct 12 ms 51720 KB Output is correct
13 Correct 658 ms 67276 KB Output is correct
14 Correct 614 ms 66976 KB Output is correct
15 Correct 608 ms 67152 KB Output is correct
16 Correct 619 ms 66940 KB Output is correct
17 Correct 621 ms 66976 KB Output is correct
18 Correct 573 ms 67924 KB Output is correct