Submission #471475

#	Time	Username	Problem	Language	Result	Execution time	Memory
471475		prvocislo	Treatment Project (JOI20_treatment)	C++17	100 / 100	865 ms	66404 KiB

treatment

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
typedef long long ll;
using namespace std;

const int maxm = 1 << 17;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > st[2][maxm * 2];
vector<int> cm[2]; // skomprimovane x suradnice
ll dist[maxm]; // vzdialenosti
int n, m;
void update(int ly, int x, int y, int i)
{
	x = lower_bound(cm[ly].begin(), cm[ly].end(), x) - cm[ly].begin();
	for (x += maxm; x > 0; x >>= 1)
		st[ly][x].push({ y, i });
}
vector<int> v;
void query(int ly, int x, int y)
{
	x = lower_bound(cm[ly].begin(), cm[ly].end(), x) - cm[ly].begin();
	for (int r = x + maxm + 1; r > 0; r >>= 1) if (r & 1)
	{
		r--;
		while (!st[ly][r].empty() && st[ly][r].top().first <= y)
		{
			int i = st[ly][r].top().second; st[ly][r].pop();
			if (!dist[i]) v.push_back(i);
		}
	}
}
struct project { int t, l, r, c; } p[maxm];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m; 
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > mini;
	for (int i = 0; i < m; i++)
	{
		cin >> p[i].t >> p[i].l >> p[i].r >> p[i].c, p[i].l--;
		if (!p[i].l) mini.push({ p[i].c, i }), dist[i] = p[i].c;
		cm[0].push_back(-p[i].t), cm[1].push_back(p[i].t);
	}
	for (int l = 0; l < 2; l++)
	{
		sort(cm[l].begin(), cm[l].end());
		for (int i = 0; i < m; i++) update(l, (l == 0 ? -p[i].t : p[i].t), (l == 0 ? p[i].l + p[i].t : p[i].l - p[i].t), i);
	}
	while (!mini.empty())
	{
		int i = mini.top().second;
		mini.pop();
		if (p[i].r == n)
		{
			cout << dist[i] << "\n";
			return 0;
		}
		v.clear();
		query(0, -p[i].t, p[i].r + p[i].t);
		query(1, p[i].t, p[i].r - p[i].t);
		for (int j : v) if (!dist[j])
		{
			//cout << i << " -> " << j << "\n";
			dist[j] = dist[i] + (ll)p[j].c;
			mini.push({ dist[j], j });
		}
	}
	cout << "-1\n";
	return 0;
}

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