oj.uz

Submission #873917

# Submission time Handle Problem Language Result Execution time Memory
873917 2023-11-16T02:44:03 Z noiaint Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 624 ms 67580 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 8 ms 51544 KB Output is correct
2 Correct 7 ms 51544 KB Output is correct
3 Correct 7 ms 51544 KB Output is correct
4 Correct 7 ms 51776 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 8 ms 51544 KB Output is correct
2 Correct 7 ms 51544 KB Output is correct
3 Correct 7 ms 51544 KB Output is correct
4 Correct 7 ms 51776 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 12 ms 51804 KB Output is correct
9 Correct 13 ms 51936 KB Output is correct
10 Correct 12 ms 51936 KB Output is correct
11 Correct 12 ms 51804 KB Output is correct
12 Correct 12 ms 51932 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51544 KB Output is correct
2 Correct 7 ms 51544 KB Output is correct
3 Correct 7 ms 51544 KB Output is correct
4 Correct 7 ms 51776 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 12 ms 51804 KB Output is correct
9 Correct 13 ms 51936 KB Output is correct
10 Correct 12 ms 51936 KB Output is correct
11 Correct 12 ms 51804 KB Output is correct
12 Correct 12 ms 51932 KB Output is correct
13 Correct 619 ms 67480 KB Output is correct
14 Correct 624 ms 67124 KB Output is correct
15 Correct 602 ms 67156 KB Output is correct
16 Correct 610 ms 66900 KB Output is correct
17 Correct 611 ms 67060 KB Output is correct
18 Correct 561 ms 67580 KB Output is correct