Submission #156988

#	Time	Username	Problem	Language	Result	Execution time	Memory
156988		faremy	Pinball (JOI14_pinball)	C++14	100 / 100	171 ms	19288 KiB

pinball

#include <iostream>
#include <algorithm>
#include <vector>


struct Reindex
{
	Reindex(int d, int e, int p) : device(d), elem(e), pos(p) {}
	int device, elem, pos;

	bool operator <(const Reindex &other) const
	{
		return (pos < other.pos);
	}
};

const int MAXN = 1e5;
const long long INFTY = 1e18;

const int LEAVES = 1 << 19;
const int TSIZE = LEAVES << 1;

int left[MAXN], right[MAXN];
int drop[MAXN];
int cost[MAXN];

std::vector<Reindex> compress;
long long tree[TSIZE];

long long getLeft[MAXN];
long long getRight[MAXN];


void reset()
{
	std::fill_n(tree, TSIZE, INFTY);
}

void upd(int node, long long val)
{
	tree[node] = std::min(tree[node], val);
	if (node > 1)
		upd(node / 2, val);
}

long long req(int leftNode, int rightNode)
{
	long long ans = INFTY;
	if (leftNode % 2 == 1)
		ans = std::min(ans, tree[leftNode++]);
	if (rightNode % 2 == 1)
		ans = std::min(ans, tree[--rightNode]);
	if (leftNode < rightNode)
		ans = std::min(ans, req(leftNode / 2, rightNode / 2));
	return ans;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int lines, columns;
	std::cin >> lines >> columns;

	for (int iDevice = 0; iDevice < lines; iDevice++)
	{
		std::cin >> left[iDevice] >> right[iDevice] >> drop[iDevice] >> cost[iDevice];
		compress.emplace_back(iDevice, 0, left[iDevice] - 1);
		compress.emplace_back(iDevice, 1, right[iDevice] - 1);
		compress.emplace_back(iDevice, 2, drop[iDevice] - 1);
	}

	compress.emplace_back(-1, -1, 0);
	compress.emplace_back(-1, -1, columns - 1);
	std::sort(compress.begin(), compress.end());
	int trueCol = 0;

	for (int iElem = 0; iElem < (int)compress.size(); trueCol++)
		for (int jElem = iElem; iElem < (int)compress.size() && compress[iElem].pos == compress[jElem].pos; iElem++)
		{
			if (compress[iElem].elem == 0)
				left[compress[iElem].device] = trueCol;
			else if (compress[iElem].elem == 1)
				right[compress[iElem].device] = trueCol + 1;
			else if (compress[iElem].elem == 2)
				drop[compress[iElem].device] = trueCol;
		}

	reset();
	upd(LEAVES, 0);

	for (int iDev = 0; iDev < lines; iDev++)
	{
		getLeft[iDev] = req(LEAVES + left[iDev], LEAVES + right[iDev]);
		upd(LEAVES + drop[iDev], getLeft[iDev] + cost[iDev]);
	}

	reset();
	upd(LEAVES + trueCol - 1, 0);

	for (int iDev = 0; iDev < lines; iDev++)
	{
		getRight[iDev] = req(LEAVES + left[iDev], LEAVES + right[iDev]);
		upd(LEAVES + drop[iDev], getRight[iDev] + cost[iDev]);
	}

	long long minCost = INFTY;
	for (int iDev = 0; iDev < lines; iDev++)
		minCost = std::min(minCost, getLeft[iDev] + getRight[iDev] + cost[iDev]);
	
	if (minCost == INFTY)
		std::cout << "-1\n";
	else
		std::cout << minCost << '\n';

	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49