제출 #465752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465752		JovanB	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	393 ms	29596 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55