Submission #991383

#	Time	Username	Problem	Language	Result	Execution time	Memory
991383		SanguineChameleon	Train (APIO24_train)	C++17	0 / 100	53 ms	19124 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

const int inf1 = 1e9 + 20;
const long long inf2 = 1e18L + 20;

struct planet {
	int L, R;
	long long cost;

	planet(long long _cost): L(-2), R(-1), cost(_cost) {};
};

struct train {
	int L, R, u, v;
	long long cost;

	train(int _L, int _R, int _u, int _v, long long _cost): L(_L), R(_R), u(_u), v(_v), cost(_cost) {};
};

struct meal {
	int L, R;

	meal(int _L, int _R, long long _cost): L(_L), R(_R) {};
};

struct event {
	int time, type, id;

	event(int _time, int _type, int _id): time(_time), type(_type), id(_id) {};
};

bool operator<(train &t1, train &t2) {
	if (t1.v != t2.v) {
		return t1.v < t2.v;
	}
	else {
		return t1.R < t2.R;
	}
}

bool operator<(meal &m1, meal &m2) {
	return m1.R > m2.R;
}

bool operator<(event &e1, event &e2) {
	if (e1.time != e2.time) {
		return e1.time < e2.time;
	}
	else {
		return e1.type < e2.type;
	}
}

bool operator<(meal &m, int x) {
	return m.R > x;
}

struct fenwick_tree {
	vector<int> sum;
	int N;

	fenwick_tree(int _N) {
		N = _N;
		sum.resize(N + 1);
	}

	void update(int pos) {
		pos++;
		for (int i = pos; i <= N; i += i & (-i)) {
			sum[i]++;
		}
	}

	int get(int pos) {
		pos++;
		int res = 0;
		for (int i = pos; i > 0; i -= i & (-i)) {
			res += sum[i];
		}
		return res;
	}
};

struct segment_tree {


};

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) {
	vector<planet> planets;
	for (int i = 0; i < N; i++) {
		planets.emplace_back(T[i]);
	}
	int planet_cnt = planets.size();
	vector<train> trains;
	for (int i = 0; i < M; i++) {
		trains.emplace_back(A[i], B[i], X[i], Y[i], C[i]);
	}
	trains.emplace_back(-1, 0, 0, 0, 0);
	trains.emplace_back(inf1, inf1 + 1, planet_cnt - 1, planet_cnt - 1, 0);
	sort(trains.begin(), trains.end());
	int train_cnt = trains.size();
	for (int i = 0; i < train_cnt; i++) {
		if (i == 0 || trains[i].v != trains[i - 1].v) {
			planets[trains[i].v].L = i;
		}
		if (i == train_cnt - 1 || trains[i].v != trains[i + 1].v) {
			planets[trains[i].v].R = i;
		}
	}
	vector<meal> meals;
	for (int i = 0; i < W; i++) {
		meals.emplace_back(L[i], R[i], T[i]);
	}
	sort(meals.begin(), meals.end());
	int meal_cnt = meals.size();
	vector<event> events;
	for (int id = 0; id < train_cnt; id++) {
		events.emplace_back(trains[id].L, 0, id);
	}
	for (int id = 0; id < meal_cnt; id++) {
		events.emplace_back(meals[id].R, 1, id);
	}
	sort(events.begin(), events.end());
	vector<long long> dp(train_cnt, inf2);
	fenwick_tree fen(meal_cnt);
	for (auto &e: events) {
		int type = e.type;
		int id = e.id;
		if (type == 0) {
			if (id == 0) {
				dp[id] = 0;
			}
			else {
				int u = trains[id].u;
				for (int i = planets[u].L; i <= planets[u].R; i++) {
					if (trains[i].R > trains[id].L) {
						break;
					}
					int pos = lower_bound(meals.begin(), meals.end(), trains[i].R) - meals.begin() - 1;
					dp[id] = min(dp[id], dp[i] + planets[u].cost * fen.get(pos) + trains[id].cost);
				}
			}
		}
		else {
			fen.update(id);
		}
	}
	long long res = dp.back();
	if (res == inf2) {
		res = -1;
	}
	return res;
}

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