oj.uz

Submission #1082236

# Submission time Handle Problem Language Result Execution time Memory
1082236 2024-08-31T00:06:23 Z tfgs Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 714 ms 29572 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }

bool same_sign(int x, int y) {
    if (!x || !y) return true;
    return x<0&&y<0 || x>0&&y>0;
}
const array<int, 4> zero = {0, 0, 0, 0};

int n;
vi d;
V<array<int, 4>> t;
array<int, 4> merge(int l, int m, int r, array<int, 4> a, array<int, 4> b) {
    array<int, 4> res = zero;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (m-l == 1 && (i == 1 || i == 2)) continue;
            if (r-m == 1 && (j == 1 || j == 2)) continue;
            if (i%2 && (j==0b10 || j == 0b11) && !same_sign(d[m-1], d[m])) continue;

            int new_shape = (i&0b10)+(j&0b01);
            ckmax(res[new_shape], a[i]+b[j]);
        }
    }
    return res;
}
void init_tree() {
    int siz = 1;
    while (siz < 2*n) siz *= 2;
    t.resize(siz, zero);
}
void point_upd(int ind, int u=0, int l=0, int r=n) {
    if (l == r-1) {
        t[u][0] = 0;
        t[u][3] = abs(d[ind]);
        return;
    }
    int m = (l+r)/2;
    if (ind < m) point_upd(ind, 2*u+1, l, m);
    else point_upd(ind, 2*u+2, m, r);
    t[u] = merge(l, m, r, t[2*u+1], t[2*u+2]);
}

void solve() {
    int q; cin >> n >> q;
    vi a(n);
    for (int& i : a) cin >> i;
    n--;
    init_tree();
    d.resize(n);
    for (int i = 0; i < n; i++) {
        d[i] = a[i+1]-a[i];
        point_upd(i);
    }
    // ps(d);
    // ps(t[0]);
    // ps(t[1], t[2], t[5], t[6]);

    while (q--) {
        int l, r, x; cin >> l >> r >> x; l--;
        if (l-1 >= 0) {
            d[l-1] += x;
            point_upd(l-1);
        }
        if (r-1 < n) {
            d[r-1] -= x;
            point_upd(r-1);
        }
        // ps(d);
        // ps(t[0]);
        cout << *max_element(all(t[0])) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'bool same_sign(int64_t, int64_t)':
Main.cpp:26:15: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |     return x<0&&y<0 || x>0&&y>0;
      |            ~~~^~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 10 ms 860 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 6 ms 860 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 663 ms 29080 KB Output is correct
14 Correct 685 ms 29012 KB Output is correct
15 Correct 663 ms 28884 KB Output is correct
16 Correct 714 ms 28988 KB Output is correct
17 Correct 703 ms 28980 KB Output is correct
18 Correct 652 ms 29572 KB Output is correct