#include <algorithm>
#include <cmath>
#include <iostream>
#include <unistd.h>
#include <vector>
using namespace std;
int N, rtN, chsize;
vector<int> mid;
vector<vector<int64_t>> ops, sums, boxes, caps;
void applyChunk(int ch) {
if (!ops[ch].size()) return;
for (int bi = 0; bi < boxes[ch].size(); bi++) {
int lo = mid[ch], hi = ops[ch].size()-1;
while (lo < hi) {
int m = (lo+hi+1)/2;
if (abs(ops[ch][m]) >= caps[ch][bi]) lo = m; else hi = m-1;
}
//cout << ch << ' ' << bi << ' ' << lo << endl;
if (abs(ops[ch][lo]) < caps[ch][bi]) {
boxes[ch][bi] = max(int64_t(0), min(caps[ch][bi], boxes[ch][bi] + sums[ch][mid[ch]]));
boxes[ch][bi] = max(int64_t(0), min(caps[ch][bi], boxes[ch][bi] + ops[ch][mid[ch]]));
boxes[ch][bi] += sums[ch].back() - sums[ch][mid[ch]+1];
} else {
if (ops[ch][lo] < 0) {
boxes[ch][bi] = sums[ch].back() - sums[ch][lo+1];
} else {
boxes[ch][bi] = caps[ch][bi] + sums[ch].back() - sums[ch][lo+1];
}
}
}
ops[ch].clear();
sums[ch].resize(1);
mid[ch] = 0;
}
void addOp(int ch, int64_t op) {
if (ops[ch].size() && ((op > 0) == (ops[ch].back() > 0))) {
ops[ch].back() += op;
sums[ch].back() += op;
} else {
ops[ch].push_back(op);
sums[ch].push_back(sums[ch].back() + ops[ch].back());
}
for (;;) {
int n = ops[ch].size();
if (n < 3 || abs(ops[ch][n-2]) > abs(ops[ch][n-1]) || abs(ops[ch][n-2]) > abs(ops[ch][n-3])) break;
int x = ops[ch][n-1] + ops[ch][n-2] + ops[ch][n-3];
ops[ch].resize(n-3);
ops[ch].push_back(x);
sums[ch].resize(n-2);
sums[ch].push_back(sums[ch].back() + ops[ch].back());
mid[ch] = min(mid[ch], n-3);
}
int n = ops[ch].size();
if (n >= 2 && abs(ops[ch][n-2]) < abs(ops[ch][n-1])) mid[ch] = n-1;
}
int main() {
while (cin >> N) {
rtN = sqrt(N);
chsize = N/rtN + 1;
ops = sums = boxes = caps = vector<vector<int64_t>>(rtN);
mid = vector<int>(rtN);
int tot = 0;
for (int i = 0; i < rtN; i++) {
boxes[i].resize(min(N-tot, chsize));
caps[i].resize(boxes[i].size());
sums[i].resize(1);
for (auto& x : caps[i]) cin >> x;
tot += boxes[i].size();
}
int Q, L, R, V;
for (cin >> Q; Q--;) {
cin >> L >> R >> V;
int c1 = L/chsize, c2 = R/chsize, c1i = L-c1*chsize, c2i = R-c2*chsize;
if (c1 == c2) {
applyChunk(c1);
for (int i = c1i; i <= c2i; i++) boxes[c1][i] = max(int64_t(0), min(caps[c1][i], boxes[c1][i] + V));
} else {
applyChunk(c1);
for (int i = c1i; i < boxes[c1].size(); i++) boxes[c1][i] = max(int64_t(0), min(caps[c1][i], boxes[c1][i] + V));
for (int ch = c1+1; ch < c2; ch++) addOp(ch, V);
applyChunk(c2);
for (int i = 0; i <= c2i; i++) boxes[c2][i] = max(int64_t(0), min(caps[c2][i], boxes[c2][i] + V));
}
/*cout << L << ' ' << R << ' ' << V << endl;
for (int ch = 0; ch < boxes.size(); ch++) {
for (auto x : boxes[ch]) cout << ' ' << x;
cout << ' ';
}
cout << endl;
for (int ch = 0; ch < boxes.size(); ch++) {
for (auto x : caps[ch]) cout << ' ' << x;
cout << ' ';
}
cout << endl;
for (int ch = 0; ch < boxes.size(); ch++) {
for (auto x : ops[ch]) cout << ' ' << x;
cout << ' ';
}
cout << endl;
for (int ch = 0; ch < boxes.size(); ch++) {
for (auto x : sums[ch]) cout << ' ' << x;
cout << ' ';
}
cout << endl;
cout << endl;*/
}
for (int ch = 0; ch < boxes.size(); ch++) applyChunk(ch);
bool first = true;
for (auto const& chunk : boxes)
for (auto x : chunk) {
if (!first) cout << ' ';
first = false;
cout << x;
}
cout << endl;
/*for (auto const& chunk : boxes)
for (auto x : chunk) {
int y;
cin >> y;
if (x != y) cerr << "ERROR!" << endl;
if (x != y) sleep(10);
}*/
}
}
Compilation message
candies.cpp: In function 'void applyChunk(int)':
candies.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int bi = 0; bi < boxes[ch].size(); bi++) {
| ~~~^~~~~~~~~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:84:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = c1i; i < boxes[c1].size(); i++) boxes[c1][i] = max(int64_t(0), min(caps[c1][i], boxes[c1][i] + V));
| ~~^~~~~~~~~~~~~~~~~~
candies.cpp:112:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int ch = 0; ch < boxes.size(); ch++) applyChunk(ch);
| ~~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccblLTgl.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3lcTZi.o:candies.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccblLTgl.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
