oj.uz

Submission #465752

# Submission time Handle Problem Language Result Execution time Memory
465752 2021-08-16T17:50:38 Z JovanB Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 393 ms 29596 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;

struct Segment{
    ll mat[2][2];
} seg[4*N+5];

ll niz[N+5];
ll b[N+5];

void mrg(int node){
    for(int i=0; i<2; i++) for(int j=0; j<2; j++) seg[node].mat[i][j] = 0;
    for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) seg[node].mat[i][j] = max(seg[node].mat[i][j], seg[node*2].mat[i][k] + seg[node*2+1].mat[k][j]);
}

void init(int node, int l, int r){
    if(l == r){
        seg[node].mat[0][0] = max(niz[l], 0LL);
        seg[node].mat[1][1] = max(-niz[l], 0LL);
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    mrg(node);
}

void upd(int node, int l, int r, int x){
    if(l == r){
        seg[node].mat[0][0] = max(niz[l], 0LL);
        seg[node].mat[1][1] = max(-niz[l], 0LL);
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x);
    else upd(node*2+1, mid+1, r, x);
    mrg(node);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
	cout.precision(10);
	cout << fixed;

	int n, qrs;
	cin >> n >> qrs;
	for(int i=1; i<=n; i++) cin >> b[i];
	for(int i=1; i<n; i++) niz[i] = b[i+1] - b[i];
	init(1, 1, n-1);
	while(qrs--){
        int l, r, x;
        cin >> l >> r >> x;
        if(l > 1){
            niz[l-1] += x;
            upd(1, 1, n-1, l-1);
        }
        if(r < n){
            niz[r] -= x;
            upd(1, 1, n-1, r);
        }
        cout << max(max(max(seg[1].mat[1][1], seg[1].mat[1][0]), seg[1].mat[0][0]), seg[1].mat[0][1]) << "\n";
	}
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 4 ms 660 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 712 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 4 ms 660 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 712 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 367 ms 28912 KB Output is correct
14 Correct 392 ms 29012 KB Output is correct
15 Correct 393 ms 28996 KB Output is correct
16 Correct 390 ms 28796 KB Output is correct
17 Correct 391 ms 28784 KB Output is correct
18 Correct 392 ms 29596 KB Output is correct