Submission #932392

#	Time	Username	Problem	Language	Result	Execution time	Memory
932392		thangdz2k7	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	390 ms	29776 KiB

Main

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 5;

int n, q;
ll d[N], a[N];

ll it[4 * N][2][2];

ll all(int s){
    ll ans = 0;
    for (int i = 0; i <= 1; ++ i){
        for (int j = 0; j <= 1; ++ j) ans = max(ans, it[s][i][j]);
    }
    return ans;
}

bool trai(ll a, ll b){
    return (a == 0 || b == 0 || (a > 0 && b < 0) || (a < 0 && b > 0));
}

void mer(int s, int mid){
    for (int i = 0; i <= 1; ++ i){
        for (int j = 0; j <= 1; ++ j) it[s][i][j] = 0;
    }
    for (int i = 0; i <= 1; ++ i){
        for (int j = 0; j <= 1; ++ j){
            for (int u = 0; u <= 1; ++ u){
                if (u & j && trai(d[mid], d[mid + 1])) continue;
                for (int v = 0; v <= 1; ++ v){
                    it[s][i][v] = max(it[s][i][v], it[2 * s][i][j] + it[2 * s + 1][u][v]);
                }
            }
        }
    }
}

void build(int s, int l, int r){
    if (l == r){
        it[s][1][1] = abs(d[l]);
        return;
    }

    int mid = l + r >> 1;
    build(2 * s, l, mid);
    build(2 * s + 1, mid + 1, r);
    mer(s, mid);
}

void upd(int s, int l, int r, int u){
    if (l == r){
        it[s][1][1] = abs(d[l]);
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) upd(2 * s, l, mid, u);
    else upd(2 * s + 1, mid + 1, r, u);
    mer(s, mid);
}

void solve(){
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        if (i > 1) d[i - 1] = a[i] - a[i - 1];
    }
    build(1, 1, n - 1);

    while (q --){
        int l, r, x;
        cin >> l >> r >> x;
        if (l > 1) {
            d[l - 1] += x;
            upd(1, 1, n - 1, l - 1);
        }
        if (r < n) {
            d[r] -= x;
            upd(1, 1, n - 1, r);
        }
        cout << all(1) << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

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

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