Submission #245944

#	Time	Username	Problem	Language	Result	Execution time	Memory
245944		faremy	Treatment Project (JOI20_treatment)	C++14	100 / 100	531 ms	140544 KiB

treatment

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


struct Endpoint
{
	int x, y, segment, color;
	bool operator <(const Endpoint &other) const
	{
		if (x != other.x)
			return (x < other.x);
		return (color < other.color);
	}
};

struct Edge
{
	Edge(int d, long long w) : dest(d), weight(w) {}
	int dest;
	long long weight;

	bool operator <(const Edge &other) const
	{
		return (other.weight < weight);
	}
};


const int MAXN = 1e5;
const int MAXG = 2e6;
const long long INFTY = 1e18;

int day[MAXN];
int left[MAXN], right[MAXN];
long long cost[MAXN];

Endpoint extr[2 * MAXN];
Endpoint bckp[2 * MAXN];

int nodes;
std::vector<Edge> graph[MAXG];
std::priority_queue<Edge> dijkstra;
long long minDist[MAXG];


void buildgraph(int first, int last)
{
	if (last - first == 1)
		return;
	int mid = (first + last) / 2;
	buildgraph(first, mid);
	buildgraph(mid, last);

	int previous = -1;
	int iLeft = first, iSort = first;
	for (int iRight = mid; iRight < last; iRight++)
	{
		while (iLeft < mid && extr[iLeft].y >= extr[iRight].y)
		{
			if (extr[iLeft].color == 0)
			{
				graph[nodes].emplace_back(extr[iLeft].segment, cost[extr[iLeft].segment]);
				if (previous != -1)
					graph[nodes].emplace_back(previous, 0);
				previous = nodes;
				nodes++;
			}

			bckp[iSort] = extr[iLeft];
			iLeft++; iSort++;
		}

		if (extr[iRight].color == 1 && previous != -1)
			graph[extr[iRight].segment].emplace_back(previous, 0);
		bckp[iSort] = extr[iRight];
		iSort++;
	}

	for (; iLeft < mid; iLeft++)
	{
		bckp[iSort] = extr[iLeft];
		iSort++;
	}

	for (int iCpy = first; iCpy < last; iCpy++)
		extr[iCpy] = bckp[iCpy];
}

void push(int node, long long dist)
{
	for (Edge &edge : graph[node])
		if (minDist[edge.dest] == INFTY)
		{
			minDist[edge.dest] = dist + edge.weight;
			if (edge.weight == 0)
				push(edge.dest, dist);
			else
				dijkstra.emplace(edge.dest, dist + edge.weight);
		}
		
}

long long findcost(int people, int treatments)
{
	std::fill_n(minDist, MAXG, INFTY);
	for (int iTreat = 0; iTreat < treatments; iTreat++)
		if (left[iTreat] == 1)
		{
			minDist[iTreat] = cost[iTreat];
			dijkstra.emplace(iTreat, cost[iTreat]);
		}

	while (!dijkstra.empty())
	{
		int node = dijkstra.top().dest;
		long long dist = dijkstra.top().weight;
		dijkstra.pop();
		push(node, dist);
	}

	long long minCost = INFTY;
	for (int iTreat = 0; iTreat < treatments; iTreat++)
		if (right[iTreat] == people)
			minCost = std::min(minCost, minDist[iTreat]);
	return minCost;
}

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

	int people, treatments;
	std::cin >> people >> treatments;

	for (int iTreat = 0; iTreat < treatments; iTreat++)
	{
		std::cin >> day[iTreat] >> left[iTreat] >> right[iTreat] >> cost[iTreat];
		extr[iTreat * 2].x = day[iTreat] + left[iTreat];
		extr[iTreat * 2].y = day[iTreat] - left[iTreat];
		extr[iTreat * 2].segment = iTreat;
		extr[iTreat * 2].color = 0;
		
		extr[iTreat * 2 + 1].x = day[iTreat] + right[iTreat] + 1;
		extr[iTreat * 2 + 1].y = day[iTreat] - right[iTreat] - 1;
		extr[iTreat * 2 + 1].segment = iTreat;
		extr[iTreat * 2 + 1].color = 1;
	}

	std::sort(extr, extr + 2 * treatments);
	nodes = 2 * treatments;
	buildgraph(0, 2 * treatments);

	long long minpay = findcost(people, treatments);
	if (minpay == INFTY)
		std::cout << "-1\n";
	else
		std::cout << minpay << '\n';

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61