QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34428#4269. Rainy MarketsQingyu#0 2ms15880kbC++203.3kb2022-06-08 22:24:312024-05-26 00:50:38

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 00:50:38]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:15880kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-08 22:24:31]
  • 提交

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%