Submission #1269513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269513		MateiKing80	Tower (JOI24_tower)	C++20	100 / 100	1008 ms	64300 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e18;
const int N = 2e5 + 5;

#define int ll


using pii = pair<int, int>;
#define fr first
#define sc second

int n, q, d, a, b;
int mincost[N];

vector<pii> liber, inter;

int findInterval(int x) {
	int pos = -1;
	for (int pas = 1 << 20; pas; pas >>= 1)
		if (pos + pas < (int)inter.size() && inter[pos + pas].fr <= x)
			pos += pas;
	return pos;
}

unordered_map<int, int> dp; //de facut map normal daca este nevoie

int dpMAX(int x) {
	int y = findInterval(x);
	if (dp[x] != 0 || x == 0)
		return dp[x];
	if (x - inter[y].fr >= d)
		return dp[x] = dpMAX(x - ((x - inter[y].fr) / d) * d) + b * ((x - inter[y].fr) / d); 
	if (y == 0)
		return a * x;
	int z = findInterval(x - d), plus = 0;
	if (x - d > inter[z].sc)
		plus += a * (x - d - inter[z].sc);
	return dp[x] = b + plus + dpMAX(min(inter[z].sc, x - d));
}

signed main() {
	dp[0] = 0;
	cin >> n >> q >> d >> a >> b;
	int last = -1;
	for (int i = 1; i <= n; i ++) {
		int l, r;
		cin >> l >> r;
		liber.push_back({last + 1, l - 1});
		last = r;
	}
	liber.push_back({last + 1, inf});
	mincost[0] = 0;
	inter.push_back(liber[0]);
	for (int i = 1; i <= n; i ++) {
		int pos = -1;
		for (int pas = 1 << 20; pas; pas >>= 1)
			if (pos + pas < (int)inter.size() && inter[pos + pas].sc + d < liber[i].fr)
				pos += pas;
		pos ++;
		if (pos != (int)inter.size() && inter[pos].fr + d <= liber[i].sc) {
			inter.push_back({max(inter[pos].fr + d, liber[i].fr), liber[i].sc});
			mincost[inter.size() - 1] = 1 + mincost[pos];
		}
	}
	while (q --) {
		int x;
		cin >> x;
		int y = findInterval(x);
		if (inter[y].sc < x) {
			cout << -1 << '\n';
		} else {
			cout << min(dpMAX(x), b * mincost[y] + a * (x - d * mincost[y])) << '\n';
		}
	}
}

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