Submission #1216025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216025		pedroslrey	Tower (JOI24_tower)	C++20	25 / 100	538 ms	58156 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

int main() {
	int n, q;
	cin >> n >> q;

	lli D, A, B;
	cin >> D >> A >> B;

	map<lli, vector<pair<lli, lli>>> blocks;
	vector<lli> levels{0};
	for (int i = 0; i < n; ++i) {
		lli l, r;
		cin >> l >> r;

		blocks[l/D].emplace_back(l%D, (r/D == l/D ? r%D : D - 1));
		if (r/D == l/D + 1) blocks[r/D].emplace_back(0, r%D);
		else if (r/D > l/D + 1) blocks[l/D + 1].emplace_back(0, D - 1);

		levels.push_back(max(l/D - 1, 0LL));
		levels.push_back(l/D);
		levels.push_back(l/D + 1);
		levels.push_back(l/D + 2);
	}

	map<lli, vector<pair<lli, int>>> queries;
	for (int i = 0; i < q; ++i) {
		lli x;
		cin >> x;

		queries[x/D].emplace_back(x%D, i);
		levels.push_back(x/D);
	}

	sort(levels.begin(), levels.end());
	levels.erase(unique(levels.begin(), levels.end()), levels.end());

	set<pair<lli, lli>> S; lli delta = 0;
	vector<lli> prevblocks;
	const lli INF = 2e18;

	auto query = [&](lli r) {
		auto it = S.upper_bound({r, INF});

		if (it == S.begin()) return INF;
		it = prev(it);
		if (it->second + delta >= INF) return INF;

		return it->second + delta + (r - it->first)*A;
	};

	auto add = [&](lli r, lli x) {
		if (x > query(r)) return;

		while (true) {
			auto it = S.lower_bound({r, -INF});
			if (it != S.end() && it->second < INF && it->second + delta > x + (it->first - r)*A) S.erase(it);
			else break;
		}

		while (true) {
			auto it = S.lower_bound({r, INF});
			if (it != S.end() && it->second < INF && it->second + delta > x + (it->first - r)*A) S.erase(it);
			else break;
		}

		S.emplace(r, x - delta);
	};

	auto add_block = [&](lli l, lli r) {
		while (true) {
			auto it = S.lower_bound({l, -INF});
			if (it != S.end() && it->first <= r) S.erase(it);
			else break;
		}
		S.emplace(l, INF);
	};

	lli lst = -1;
	S.emplace(0, -B);
	if (D > 1) {
		S.emplace(1, INF);
		prevblocks.push_back(1);
	}

	vector<lli> ans(q);
	for (lli x: levels) {
		vector<pair<lli, lli>> fins;
		bool ok = true;
		for (auto [l, r]: blocks[x]) {
			// cerr << "block " << x << " " << l << " " << r << "\n";
			if (l == 0) ok = false; 
			if (r + 1 < D) fins.emplace_back(r + 1, query(r + 1) + (x - lst)*B);
		}
		if (ok && x > 0) fins.emplace_back(0, min(query(0) + (x - lst)*B, query(D - 1) + (x - lst - 1)*D*A + A));

		for (lli r: prevblocks)
			S.erase({r, INF});
		prevblocks.clear();

		// cerr << "fins: ";
		// for (auto [r, x]: fins)
		// 	cerr << "(" << r << ", " << x << ") ";
		// cerr << "\n";

		delta += (x - lst)*B;
		lst = x;
		for (auto [l, r]: blocks[x]) {
			prevblocks.push_back(l);
			add_block(l, r);
		}

		sort(fins.rbegin(), fins.rend());

		for (auto [r, x]: fins)
			if (x + delta < INF) add(r, x);
		
		for (auto [r, idx]: queries[x]) {
			lli x = query(r);
			ans[idx] = (x >= INF ? -1 : x);
		}

		// cerr << "-> " << x << "\n";
		// for (auto [r, x]: S)
		// 	cerr << "(" << r << ", " << x + delta << ")\n";
		// cerr << "\n";
	}

	for (lli x: ans)
		cout << x << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 25 / 25
• Subtask 4: 0 / 32