Submission #1259985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259985		antromancap	Train (APIO24_train)	C++20	100 / 100	198 ms	48900 KiB

train

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;
const int N = 1e5 + 1;
int n, m, w, cost[N], meal2[N], cnt = 0, cur = 0;
long long dist[N];
set<pair<long long, int>> city[N];
vector<int> g[N];
priority_queue<pair<int, int>> q;
int rt[N], ls[30 * N], rs[30 * N], it[30 * N];

struct Edge {
	int x, y, a, b, c;
	bool operator<(const Edge &u) const { return a < u.a; }
} e[N];

struct Meal {
	int l, r, id;
} meal[N];

bool cmp1(const Meal &x, const Meal &y) { return make_pair(x.r, x.l) < make_pair(y.r, y.l); }
bool cmp2(const Meal &x, const Meal &y) { return x.l < y.l; }

void upd(int i, int old, int l, int r, int p) {
	it[i] = it[old] + 1;
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (p <= mid) {
		rs[i] = rs[old];
		upd(ls[i] = ++cnt, ls[old], l, mid, p);
	} else {
		ls[i] = ls[old];
		upd(rs[i] = ++cnt, rs[old], mid + 1, r, p);
	}
}

int query(int i, int l, int r, int u, int v) {
	if (!i || l > v || r < u) return 0;
	if (u <= l && r <= v) return it[i];
	int mid = (l + r) >> 1;
	return query(ls[i], l, mid, u, v) + query(rs[i], mid + 1, r, u, v);
}

long long getval(int i) {
	long long res = dist[i];
	if (cur == 0) return res;
	int p = upper_bound(meal2, meal2 + w, e[i].b) - meal2;
	long long cnt = cur;
	if (p) cnt -= query(rt[p - 1], 0, w - 1, 0, cur - 1);
	assert(cnt >= 0);
	return res + cnt * cost[e[i].y];
}

int findkth(int i, int j, int l, int r, int k) {
	if (l == r) return l;
	int mid = (l + r) >> 1, t = it[ls[j]] - it[ls[i]];
	if (k <= t) return findkth(ls[i], ls[j], l, mid, k);
	return findkth(rs[i], rs[j], mid + 1, r, k - t);
}

int getkth(int l, int r, long long k) {
	l = lower_bound(meal2, meal2 + w, l) - meal2;
	r = upper_bound(meal2, meal2 + w, r) - meal2;
	if (!r || r - l < k) return -1;
	return findkth(l ? rt[l - 1] : 0, rt[r - 1], 0, w - 1, k);
}

void calc(int i) {
	int v = e[i].y;
	int j = prev(city[v].find(make_pair(dist[i], i)))->second;
	long long dif = dist[i] - dist[j];
	long long k = (dif + cost[v] - 1) / cost[v];
	int kth = getkth(e[j].b + 1, e[i].b, k);
	if (kth != -1) g[kth].push_back(i), assert(kth >= cur);
}

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
	n = N, m = M, w = W;
	for (int i = 0; i < n; i++) cost[i] = T[i];
	for (int i = 0; i < m; i++) e[i] = { X[i], Y[i], A[i], B[i], C[i] };
	sort(e, e + m);
	for (int i = 0; i < w; i++) meal[i] = { L[i], R[i], 0 };
	sort(meal, meal + w, cmp1);
	for (int i = 0; i < w; i++) meal[i].id = i;
	sort(meal, meal + w, cmp2);
	for (int i = 0; i < w; i++) {
		upd(rt[i] = ++cnt, i ? rt[i - 1] : 0, 0, w - 1, meal[i].id);
		meal2[i] = meal[i].l;
	}
	sort(meal, meal + w, cmp1);
	memset(dist, -1, 8 * m);
	city[0].insert(make_pair(0, m));
	e[m].b = -1;
	bool ok = 0;
	for (int i = 0; i < m; i++) {
		if (i == 250) ok = 1;
		while (cur < w && meal[cur].r < e[i].a) {
			cur++;
			for (int j : g[cur - 1]) {
				int v = e[j].y;
				auto it = city[v].find(make_pair(dist[j], j));
				if (it == city[v].end()) continue;
				while (it != city[v].begin() && getval(prev(it)->second) >= getval(j)) city[v].erase(prev(it));
				if (it != city[v].begin()) calc(j);
			}
		}
		while (q.size() && -q.top().first <= e[i].a) {
			int j = q.top().second;
			q.pop();
			int v = e[j].y;
			while (city[v].size() && getval(city[v].rbegin()->second) >= getval(j)) city[v].erase(--city[v].end());
			city[v].insert(make_pair(dist[j], j));
			if (city[v].size() > 1) calc(j);
		}
		int u = e[i].x;
		if (city[u].empty()) continue;
		dist[i] = getval(city[u].begin()->second) + e[i].c;
		q.push(make_pair(-e[i].b, i));
	}

	cur = w;
	long long res = inf;
	for (int i = 0; i < m; i++)
		if (e[i].y == n - 1 && dist[i] != -1) res = min(res, getval(i));
	return res < inf ? res : -1;
}

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