oj.uz

Submission #440320

# Submission time Handle Problem Language Result Execution time Memory
440320 2021-07-02T04:24:11 Z SirCovidThe19th Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1411 ms 26220 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)

const ll mx1 = 2e5+5, mx2 = (1<<18), inf = LLONG_MAX/2;

ll n, q, sz, diff[mx1], mid[mx2], seg[mx2*2][2][2];

void upd(ll i, ll val){
    i += sz; seg[i][1][0] = seg[i][0][1] = -inf; seg[i][1][1] = abs(val);
    auto sgn = [](ll val){ return (val < 0) ? -1 : 1; };
    for (i /= 2; i > 0; i /= 2){
        FOR(l, 0, 2) FOR(r, 0, 2){ ll& curr = seg[i][l][r]; curr = -inf;
            curr = max(curr, seg[i*2][l][0]+seg[i*2+1][0][r]);
            curr = max(curr, seg[i*2][l][1]+seg[i*2+1][0][r]);
            curr = max(curr, seg[i*2][l][0]+seg[i*2+1][1][r]);
            if (sgn(diff[mid[i]])*sgn(diff[mid[i]+1]) != -1)
                curr = max(curr, seg[i*2][l][1]+seg[i*2+1][1][r]);
        }
    }
}

int main(){ 
    cin >> n >> q; sz = pow(2, ceil(log2(n-1)));
    FOR(i, 1, sz){
        int l = i, r = i; 
        while (r < sz) l = l*2, r = r*2+1;
        mid[i] = (l+r)/2-sz; mid[i] = min(mid[i], mx1-1);
    }ll prev; FOR(i, 0, n){ 
        ll a; cin >> a;
        if (i > 0) diff[i-1] = a-prev, upd(i-1, diff[i-1]); 
        prev = a;
    }while (q--){
        ll l, r, x; cin >> l >> r >> x; l--; r--;
        if (l-1 >= 0) diff[l-1] += x, upd(l-1, diff[l-1]);
        if (r < n-1) diff[r] -= x, upd(r, diff[r]);
        cout<<max({seg[1][0][0], seg[1][1][0], seg[1][0][1], seg[1][1][1]})<<endl;
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 14 ms 704 KB Output is correct
8 Correct 18 ms 688 KB Output is correct
9 Correct 14 ms 704 KB Output is correct
10 Correct 16 ms 672 KB Output is correct
11 Correct 15 ms 588 KB Output is correct
12 Correct 19 ms 708 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 14 ms 704 KB Output is correct
8 Correct 18 ms 688 KB Output is correct
9 Correct 14 ms 704 KB Output is correct
10 Correct 16 ms 672 KB Output is correct
11 Correct 15 ms 588 KB Output is correct
12 Correct 19 ms 708 KB Output is correct
13 Correct 1411 ms 25564 KB Output is correct
14 Correct 1343 ms 25612 KB Output is correct
15 Correct 1363 ms 25540 KB Output is correct
16 Correct 1293 ms 25708 KB Output is correct
17 Correct 1314 ms 25408 KB Output is correct
18 Correct 1247 ms 26220 KB Output is correct