oj.uz

Submission #497862

# Submission time Handle Problem Language Result Execution time Memory
497862 2021-12-24T02:05:18 Z hoanghq2004 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 481 ms 29512 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;
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

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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 4 ms 720 KB Output is correct
8 Correct 4 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 4 ms 708 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 764 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 4 ms 720 KB Output is correct
8 Correct 4 ms 720 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 4 ms 708 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 764 KB Output is correct
13 Correct 440 ms 29080 KB Output is correct
14 Correct 480 ms 28940 KB Output is correct
15 Correct 424 ms 28984 KB Output is correct
16 Correct 431 ms 28884 KB Output is correct
17 Correct 481 ms 28932 KB Output is correct
18 Correct 399 ms 29512 KB Output is correct