제출 #1127976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127976		notkai	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	1088 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
vector<int> diff(MAXN-1);
bool opposite(int x, int y) {
    if (x>0 && y > 0) {
        return true;
    }
    if (x < 0 && y < 0) {
        return true;
    }
    return false;
}
namespace SegmentTree{
    int segtree[MAXN * 4][4];
    int n;
    void update(int index, int value, int onleft=0, int onright=n-1, int treeindex=0){
        if (onleft > index || onright < index){
            return;
        }
        if (onleft == onright){
            segtree[treeindex][0] = abs(value);
            segtree[treeindex][1] = -1;
            segtree[treeindex][2] = -1;
            segtree[treeindex][3] = 0;
            return;
        }

        update(index, value, onleft, (onleft+onright)/2, treeindex*2+1);
        update(index, value, (onleft+onright+2)/2, onright, treeindex*2+2);
        segtree[treeindex][0] = -1;
        segtree[treeindex][1] = -1;
        segtree[treeindex][2] = -1;
        segtree[treeindex][3] = -1;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (segtree[treeindex*2+1][i] == -1 || segtree[treeindex*2+2][j] == -1) {
                    continue;
                }
                if ((opposite(diff[(onleft+onright)/2], diff[(onleft+onright+2)/2])) && (i%2==0) && (j/2 == 0)) {
                    continue;
                }
                segtree[treeindex][2*(i/2) + (j%2)] = segtree[treeindex*2+1][i] + segtree[treeindex*2+2][j];
            }
        }
    }
    void initialize(int maxn){
        n = maxn;
        for (int i = 0; i < 4*n; i++){
            segtree[i][0] = 0;
            segtree[i][1] = 0;
            segtree[i][2] = 0;
            segtree[i][3] = 0;
        }
    }
} //addition, 1 based indexing, range queries + point updates
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q; cin >> n >> q;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (i > 0) {
            diff[i-1] = arr[i] - arr[i-1];
        }
    }
    SegmentTree::initialize(n-1);
    for (int i = 0; i < n-1; i++) {
        SegmentTree::update(i, diff[i]);
    }
    for (int query = 0; query < q; query++) {
        int l,r,x; cin >> l >> r >> x;
        l -= 1;
        r -= 1;
        if (r < n-1) {
            diff[r] -= x;
            SegmentTree::update(r, diff[r]);
        }
        if (l > 0) {
            diff[l-1] += x;
            SegmentTree::update(l-1, diff[l]);
        }
        //value is new value not diff
        int maxans = 0;
        for (int i = 0; i < 4; i++) {
            maxans = max(maxans, SegmentTree::segtree[0][i]);
        }
        cout << maxans << "\n";
    }



}

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