Submission #220222

#	Time	Username	Problem	Language	Result	Execution time	Memory
220222		atoiz	Treatment Project (JOI20_treatment)	C++14	100 / 100	183 ms	8944 KiB

treatment

/*input
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <time.h>

using namespace std;

const int64_t INFLL = 1e17;
const int MAXN = 100007, INF = 2e9 + 9;
int N, M, T[MAXN], R[MAXN], L[MAXN], C[MAXN];
int64_t dist[MAXN];

struct Point
{ 
	int x, y, id; 
	Point (int _x, int _y, int _id): x(_x), y(_y), id(_id) {}
};
// bool compY(const Point &p, const Point &q) { return p.y == q.y ? p.x < q.x : p.y < q.y; }

vector<Point> pnts;
int min_y[MAXN << 2];
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;

void build(int rt = 1, int lo = 0, int hi = M - 1)
{
	if (lo == hi) {
		min_y[rt] = pnts[lo].y;
		return;
	}

	int md = (lo + hi) >> 1;
	build(rt << 1, lo, md);
	build(rt << 1 | 1, md + 1, hi);
	min_y[rt] = min(min_y[rt << 1], min_y[rt << 1 | 1]);
}

void upd(int rx, int ry, int64_t val, int rt = 1, int lo = 0, int hi = M - 1)
{
	if (rx < pnts[lo].x || min_y[rt] > ry) return;
	if (pnts[hi].x <= rx && lo == hi) {
		int id = pnts[lo].id;
		if (dist[id] > val + C[id]) {
			dist[id] = val + C[id];
			pq.emplace(dist[id], id);
		}
		min_y[rt] = INF;
		return;
	}

	int md = (lo + hi) >> 1;
	upd(rx, ry, val, rt << 1, lo, md);
	upd(rx, ry, val, rt << 1 | 1, md + 1, hi);
	min_y[rt] = min(min_y[rt << 1], min_y[rt << 1 | 1]);
}

int main()
{
	// freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	pnts.reserve(M);
	for (int i = 1; i <= M; ++i) {
		cin >> T[i] >> L[i] >> R[i] >> C[i];
		pnts.emplace_back(L[i] - T[i], L[i] + T[i], i);
	}
	sort(pnts.begin(), pnts.end(), [&](const Point &p, const Point &q) { return p.x == q.x ? p.y < q.y : p.x < q.x; });

	build();
	for (int i = 1; i <= M; ++i) {
		if (L[i] == 1) {
			dist[i] = C[i];
			pq.emplace(dist[i], i);
		} else {
			dist[i] = INFLL;
		}
	}

	while (!pq.empty()) {
		int u = pq.top().second;
		assert(dist[u] == pq.top().first);
		pq.pop();
		upd(1 + R[u] - T[u], 1 + R[u] + T[u], dist[u]);
	}

	int64_t ans = INFLL;
	for (int i = 1; i <= M; ++i) if (R[i] == N) {
		ans = min(ans, dist[i]);
	}
	if (ans == INFLL) ans = -1;
	cout << ans << endl;
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

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