제출 #1291088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291088		khoavn2008	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	174 ms	21320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define size(v) ((int)(v).size())
#define MASK(x) (1 << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 2e5 + 10, INF = (ll)1e18 + (ll)1e17, LOG = 20;

ll n,q,a[N],st[N * 4][2][2];

void merge(int c,int l,int r){
    REP(x,2)REP(y,2)st[c][x][y] = max(st[l][x][0] + st[r][0][y],st[l][x][1] + st[r][1][y]);
}
void build(int id = 1,int l = 1,int r = n){
    if(l == r){
        if(a[l] < 0)st[id][0][0] = -a[l];
        else st[id][1][1] = +a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    merge(id, id * 2, id * 2 + 1);
}
void update(int p,int id = 1,int l = 1,int r = n){
    if(p < l || r < p)return;
    if(l == r){
        REP(x,2)REP(y,2)st[id][x][y] = 0;
        if(a[l] < 0)st[id][0][0] = -a[l];
        else st[id][1][1] = +a[l];
        return;
    }
    int mid = (l + r) >> 1;
    update(p, id * 2, l, mid);
    update(p, id * 2 + 1, mid + 1, r);
    merge(id, id * 2, id * 2 + 1);
}
void printTree(int id = 1,int l = 1,int r = n){
    cout<<id<<' '<<l<<' '<<r<<":"<<st[id][0][0]<<' '<<st[id][0][1]<<' '<<st[id][1][0]<<' '<<st[id][1][1]<<endl;
    if(l == r)return;
    int mid = (l + r) >> 1;
    printTree(id * 2, l, mid);
    printTree(id * 2 + 1, mid + 1, r);
}
int main(){
//    freopen(".inp", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    FOR(i,1,n)cin>>a[i];
    FOR(i,1,n - 1)a[i] = a[i + 1] - a[i];
    n--;
    build();
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        if(l != 1)a[l - 1] += x, update(l - 1);
        if(r != n + 1)a[r] -= x, update(r);
        cout<<max({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]})<<endl;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55