oj.uz

Submission #981787

# Submission time Handle Problem Language Result Execution time Memory
981787 2024-05-13T14:54:54 Z a_l_i_r_e_z_a Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 259 ms 29084 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 2e5 + 5;
const int inf = 1e9 + 7;
int n, q, a[maxn];
struct D{
    ll ans = 0, a = 0, b = 0, dpl = 0, dpr = 0, dplr = 0;
} node[maxn * 4];

D merge(D l, D r){
    bool u = (l.b >= 0), v = (r.a >= 0);
    D res;
    res.a = l.a;
    res.b = r.b;
    if(u == v){
        res.ans = l.ans + r.ans;
        res.dpl = l.dpl + r.ans;
        res.dpr = r.dpr + l.ans;
        res.dplr = l.dpl + r.dpr;
    }
    else{
        res.ans = max(l.ans + r.dpl, l.dpr + r.ans);
        res.dpl = max(l.dpl + r.dpl, l.dplr + r.ans);
        res.dpr = max(r.dpr + l.dpr, l.ans + r.dplr);
        res.dplr = max(l.dpl + r.dplr, l.dplr + r.dpr);
    }
    return res;
}

void build(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        int x = a[r] - a[l];
        node[id].ans = abs(x);
        node[id].a = node[id].b = x;
        node[id].dpl = node[id].dpr = node[id].dplr = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    node[id] = merge(node[id * 2], node[id * 2 + 1]);
}

void upd(int p, int x, int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        node[id].a = node[id].b = node[id].a + x;
        node[id].ans = abs(node[id].a);
        return;
    }
    int mid = (l + r) / 2;
    if(p < mid) upd(p, x, l, mid, id * 2);
    else upd(p, x, mid, r, id * 2 + 1);
    node[id] = merge(node[id * 2], node[id * 2 + 1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    n--;
    build();
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        l--, r--;
        if(l) upd(l - 1, x);
        if(r < n) upd(r, -x);
        cout << node[1].ans << '\n';
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2648 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2648 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 247 ms 28820 KB Output is correct
14 Correct 247 ms 28752 KB Output is correct
15 Correct 259 ms 29084 KB Output is correct
16 Correct 256 ms 28960 KB Output is correct
17 Correct 245 ms 28816 KB Output is correct
18 Correct 222 ms 29008 KB Output is correct