QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#34428 | #4269. Rainy Markets | Qingyu# | 0 | 2ms | 15880kb | C++20 | 3.3kb | 2022-06-08 22:24:31 | 2024-05-26 00:50:38 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 2e6 + 50;
inline int lc(int o) { return o << 1; }
inline int rc(int o) { return o << 1 | 1; }
int64_t mn[N << 2], a[N << 2], tag[N << 2];
int64_t n, lim, B[N], P[N], U[N], up[N];
void maintain(int o, int64_t v) {
mn[o] += v;
tag[o] += v;
}
void push_up(int o) {
mn[o] = std::min(mn[lc(o)], mn[rc(o)]);
}
void push_down(int o) {
if (tag[o]) {
maintain(lc(o), tag[o]);
maintain(rc(o), tag[o]);
tag[o] = 0;
}
}
void build(int o, int l, int r) {
if (l == r) {
maintain(o, a[l]);
}
else {
const int mid = l + r >> 1;
build(lc(o), l, mid);
build(rc(o), mid + 1, r);
push_up(o);
}
}
int64_t query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return mn[o];
const int mid = l + r >> 1;
push_down(o);
int64_t ret = 1e18;
if (ql <= mid)
ret = std::min(ret, query(lc(o), l, mid, ql, qr));
if (qr > mid)
ret = std::min(ret, query(rc(o), mid + 1, r, ql, qr));
return ret;
}
void add(int o, int l, int r, int ql, int qr, int64_t v) {
if (ql <= l && r <= qr) {
maintain(o, v);
return;
}
const int mid = l + r >> 1;
push_down(o);
if (ql <= mid) add(lc(o), l, mid, ql, qr, v);
if (qr > mid) add(rc(o), mid + 1, r, ql, qr, v);
push_up(o);
}
int64_t query(int x, int y) {
if (x == y) return 1e18;
assert(x <= y);
return query(1, 1, lim, x, y - 1);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n;
for (int i = 1; i <= n; ++i) std::cin >> B[i];
for (int i = 1; i < n; ++i) std::cin >> P[i];
for (int i = 1; i < n; ++i) std::cin >> U[i];
lim = 2 * n - 2;
for (int i = 1; i < n; ++i) {
a[2 * i - 1] = 1e18;
a[2 * i] = 0;
}
for (int i = 1; i <= n; ++i) {
up[2 * i - 1] = B[i];
}
for (int i = 1; i < n; ++i) {
up[2 * i] = U[i];
}
build(1, 1, lim);
std::vector<int> cost0, cost1;
int64_t ans = 0;
auto impossible = [&]() {
std::cout << "NO\n";
exit(0);
};
for (int i = 1; i < n; ++i) {
// left station: 2 * i - 1
// current position: 2 * i
// right station: 2 * i + 1
// edge from the current vertex to the left station: 2 * i - 1
// edge from the current vertex to the right station: 2 * i
cost0.push_back(2 * i - 1);
cost1.push_back(2 * i);
int64_t total = P[i];
int64_t v1 = std::min(total, up[2 * i + 1]);
//printf("i = %d, total = %lld, v1 = %lld\n", i, total, v1);
total -= v1; up[2 * i + 1] -= v1;
add(1, 1, lim, 2 * i, 2 * i, v1);
if (!total) continue;
while (total) {
int x = -1; int64_t cc = 0;
if (!cost0.empty()) {
x = cost0.back(); cost0.pop_back();
cc = 0;
}
else if (!cost1.empty()) {
x = cost1.back(); cost1.pop_back();
cc = 1;
}
else impossible();
//printf("x = %d, cost = %d\n", x, cc);
int64_t e = std::min(std::min(up[x], total), query(1, 1, lim, x, 2 * i));
//printf("e = %lld\n", e);
if (!e) continue;
total -= e;
up[x] -= e;
ans += cc * e;
if (!total) {
if (cc == 0) cost0.push_back(x);
else cost1.push_back(x);
}
add(1, 1, lim, x, 2 * i, -e);
}
}
std::cout << "YES\n" << ans << '\n';
for (int i = 1; i < n; ++i) {
int64_t n_left = B[i] - up[2 * i - 1];
int64_t n_cur = U[i] - up[2 * i];
int64_t n_right = P[i] - n_left - n_cur;
std::cout << n_left << " " << n_cur << " " << n_right << '\n';
up[2 * i + 1] += n_right;
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 15880kb
input:
3 10 15 10 20 20 0 0
output:
NO
result:
ok IMPOSSIBLE
Test #2:
score: -5
Wrong Answer
time: 0ms
memory: 15716kb
input:
2 813741488 132495829 946237313 0
output:
NO
result:
wrong answer read 'NO' but expected 'YES'
Subtask #2:
score: 0
Wrong Answer
Test #36:
score: 5
Accepted
time: 0ms
memory: 15844kb
input:
3 10 15 10 20 20 0 11
output:
YES 5 10 0 10 5 5 10
result:
ok good plan
Test #37:
score: -5
Wrong Answer
time: 2ms
memory: 15752kb
input:
4 5 3 1 2 7 6 2 3 2 4
output:
NO
result:
wrong answer read 'NO' but expected 'YES'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%