#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++;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
