Submission #497862

#	Time	Username	Problem	Language	Result	Execution time	Memory
497862		hoanghq2004	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	481 ms	29512 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define HaiYen

using namespace std;

const int N = 3e5 + 10;

int n, q;
long long st[N * 4][2][2];
long long d[N], a[N];

void add(int id, int L, int R, int i) {
//    assert(i >= L && i < R);
    if (R - L == 1) {
        st[id][1][1] = abs(d[i]);
        return;
    }
    int mid = L + R >> 1;
    if (i < mid) add(id * 2, L, mid, i);
    else add(id * 2 + 1, mid, R, i);
    int con = (d[mid] >= 0) ^ (d[mid - 1] >= 0);
    for (int sL = 0; sL < 2; ++sL)
        for (int sR = 0; sR < 2; ++sR) st[id][sL][sR] = 0;
    for (int sL = 0; sL < 2; ++sL)
        for (int sR = 0; sR < 2; ++sR)
            for (int pL = 0; pL < 2; ++pL)
                for (int pR = 0; pR < 2; ++pR) {
                    if (con && sR && pL) continue;
                    st[id][sL][pR] = max(st[id][sL][pR], st[id * 2][sL][sR] + st[id * 2 + 1][pL][pR]);
                }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) d[i] = a[i + 1] - a[i];
    for (int i = 1; i < n; ++i) add(1, 1, n, i);
    while (q--) {
        int L, R, x;
        cin >> L >> R >> x;
        d[L - 1] += x;
        d[R] -= x;
        if (L - 1 > 0) add(1, 1, n, L - 1);
        if (R < n) add(1, 1, n, R);
        cout << max({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]}) << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void add(int, int, int, int)':
Main.cpp:20:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid = L + R >> 1;
      |               ~~^~~

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