Submission #937708

#	Time	Username	Problem	Language	Result	Execution time	Memory
937708		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	494 ms	30648 KiB

Main

/* In the name of God */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 2e5 + 5;

ll seg[MAXN << 2][2][2], a[MAXN], dif[MAXN];
#define lc id << 1
#define rc id << 1 | 1

bool same(int i, int j){
    if (dif[i] < 0 && dif[j] > 0) return 0;
    if (dif[i] > 0 && dif[j] < 0) return 0;
    return 1;
}

void build(int id, int l, int r){
    if (r - l == 1){
        seg[id][1][1] = abs(dif[l]);
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            for (int ii = 0; ii < 2; ii++){
                for (int jj = 0; jj < 2; jj++){
                    if (ii == jj && ii == 1){
                        if (same(mid - 1, mid)) seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    } else {
                        seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    }
                }
            }
        }
    }
}

void upd(int id, int l, int r, int ql, int qr, int delta){
    if (ql >= r || qr <= l) return;
    if (l >= ql && r <= qr){
        dif[l] += delta;
        seg[id][1][1] = abs(dif[l]);
        return;
    }
    int mid = l + r >> 1;
    upd(lc, l, mid, ql, qr, delta);
    upd(rc, mid, r, ql, qr, delta);
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            seg[id][i][j] = 0;
            for (int ii = 0; ii < 2; ii++){
                for (int jj = 0; jj < 2; jj++){
                    if (ii == jj && ii == 1){
                        if (same(mid - 1, mid)) seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    } else {
                        seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    }
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        dif[i] = a[i] - a[i + 1];
    }
    build(1, 1, n);
    while (q--){
        int l, r, x;
        cin >> l >> r >> x;
        if (l != 1) upd(1, 1, n, l - 1, l, -x);
        if (r != n) upd(1, 1, n, r, r + 1, +x);
        ll ans = 0;
        for (int i : {0, 1}) for (int j : {0, 1}) ans = max(ans, seg[1][i][j]);
        cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55