| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 440798 | SnapDragon | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}*/
}
}