oj.uz

Submission #497859

# Submission time Handle Problem Language Result Execution time Memory
497859 2021-12-24T02:00:13 Z hoanghq2004 Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 1 ms 320 KB 
#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;
int st[N * 4][2][2];
int d[N], a[N];

void add(int id, int L, int R, int i) {
    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][sR], 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

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -