oj.uz

답안 #404857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404857 2021-05-15T07:28:51 Z fvogel499 Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 1 ms 300 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define ll long long
#define rint int32_t

const int pow2 = 1<<2;

int ins [pow2*2];
int lftMin [pow2*2];
int lftMax [pow2*2];
int rgtMin [pow2*2];
int rgtMax [pow2*2];
bool oneBlock [pow2*2];
int lazyP [pow2*2];
set<int> borderNodes;

void btClear() {
    for (int i = 0; i < pow2*2; i++) {
        ins[i] = 0;
        lftMin[i] = 0;
        lftMax[i] = 0;
        rgtMin[i] = 0;
        rgtMax[i] = 0;
        if (i >= pow2) oneBlock[i] = true;
        else oneBlock[i] = false;
        lazyP[i] = 0;
    }
}

void btLazyPropag(int qNode) {
    lftMin[qNode] += lazyP[qNode];
    lftMax[qNode] += lazyP[qNode];
    rgtMin[qNode] += lazyP[qNode];
    rgtMax[qNode] += lazyP[qNode];
    if (qNode < pow2) {
        lazyP[qNode*2] += lazyP[qNode];
        lazyP[qNode*2+1] += lazyP[qNode];
    }
    lazyP[qNode] = 0;
}

void btUpdate(int rBegin, int rEnd, int rUpdate, int qNode, int qBegin, int qEnd) {
    if (rBegin > qEnd or rEnd < qBegin) btLazyPropag(qNode);
    else if (rBegin <= qBegin and qEnd <= rEnd) {
        lazyP[qNode] += rUpdate;
        btLazyPropag(qNode);
    }
    else {
        btLazyPropag(qNode);

        int qMid = (qBegin+qEnd)/2;
        btUpdate(rBegin, rEnd, rUpdate, qNode*2, qBegin, qMid);
        btUpdate(rBegin, rEnd, rUpdate, qNode*2+1, qMid+1, qEnd);

        if (borderNodes.find(qNode) == borderNodes.end() or borderNodes.find(2*qNode) == borderNodes.end()) {
            ins[qNode] = ins[qNode*2]+ins[qNode*2+1];
            int centerUnion = max(rgtMax[qNode*2], lftMax[qNode*2+1])-min(rgtMin[qNode*2], lftMin[qNode*2+1]);
            bool centerUnionRem = false;
            int centerSep = rgtMax[qNode*2]-rgtMin[qNode*2]+lftMax[qNode*2+1]-lftMin[qNode*2+1];
            ins[qNode] += max(centerUnion, centerSep);
            if (oneBlock[qNode*2] and centerUnion > centerSep) {
                lftMin[qNode] = min(lftMin[qNode*2], lftMin[qNode*2+1]);
                lftMax[qNode] = max(lftMax[qNode*2], lftMax[qNode*2+1]);
                ins[qNode] -= centerUnion;
                centerUnionRem = true;
            }
            else {
                lftMin[qNode] = lftMin[qNode*2];
                lftMax[qNode] = lftMax[qNode*2];
                if (oneBlock[qNode*2]) {
                    ins[qNode] -= rgtMax[qNode*2]-rgtMin[qNode*2];
                }
            }
            if (oneBlock[qNode*2+1] and centerUnion > centerSep) {
                rgtMin[qNode] = min(rgtMin[qNode*2+1], rgtMin[qNode*2]);
                rgtMax[qNode] = max(rgtMax[qNode*2+1], rgtMax[qNode*2]);
                if (!centerUnionRem) ins[qNode] -= centerUnion;
            }
            else {
                rgtMin[qNode] = rgtMin[qNode*2+1];
                rgtMax[qNode] = rgtMax[qNode*2+1];
                if (oneBlock[qNode*2+1]) {
                    ins[qNode] -= lftMax[qNode*2+1]-lftMin[qNode*2+1];
                }
            }
            if (oneBlock[qNode*2] and oneBlock[qNode*2+1] and centerUnion > centerSep) {
                oneBlock[qNode] = true;
            }
            else {
                oneBlock[qNode] = false;
            }
        }
        else {
            ins[qNode] = ins[qNode*2];
            lftMin[qNode] = lftMin[qNode*2];
            lftMax[qNode] = lftMax[qNode*2];
            rgtMin[qNode] = rgtMin[qNode*2];
            rgtMax[qNode] = rgtMax[qNode*2];
            oneBlock[qNode] = oneBlock[qNode*2];
        }
    }
}

rint main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int n, nbReq;
    cin >> n >> nbReq;

    int cn = n-1+pow2;
    while (cn != 0) {
        borderNodes.insert(cn);
        cn /= 2;
    }

    btClear();
    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        btUpdate(i, i, l, 1, 0, pow2-1);
    }
    for (int i = 0; i < nbReq; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--;
        r--;
        btUpdate(l, r, x, 1, 0, pow2-1);
        if (oneBlock[1]) cout << lftMax[1]-lftMin[1];
        else cout << ins[1]+lftMax[1]-lftMin[1]+rgtMax[1]-rgtMin[1];
        cout << endl;
    }

    int d = 0;
    d++;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -