oj.uz

Submission #981790

# Submission time Handle Problem Language Result Execution time Memory
981790 2024-05-13T14:58:09 Z a_l_i_r_e_z_a Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 265 ms 29008 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 4 ms 2544 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 4 ms 2544 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 252 ms 28868 KB Output is correct
14 Correct 249 ms 28756 KB Output is correct
15 Correct 265 ms 28828 KB Output is correct
16 Correct 253 ms 28752 KB Output is correct
17 Correct 246 ms 28760 KB Output is correct
18 Correct 248 ms 29008 KB Output is correct