oj.uz

Submission #991492

# Submission time Handle Problem Language Result Execution time Memory
991492 2024-06-02T10:12:25 Z SanguineChameleon Train (APIO24_train) C++17
100 / 100
 714 ms 28224 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

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

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

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

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

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

struct meal {
	int L, R;

	meal(int _L, int _R): 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.L > m2.L;
}

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.L > x;
}

bool operator<(train &t, int x) {
	return t.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 {
	struct node {
		long long min;
		long long lazy;

		node(): min(inf2), lazy(0) {};
	};

	vector<node> tree;
	int N;

	void init(int _N) {
		N = _N;
		tree.resize(N << 2);
	}

	void shift(int id, long long delta) {
		tree[id].min += delta;
		tree[id].lazy += delta;
	}

	void push(int id) {
		shift(id << 1, tree[id].lazy);
		shift(id << 1 | 1, tree[id].lazy);
		tree[id].lazy = 0;
	}

	void merge(int id) {
		tree[id].min = min(tree[id << 1].min, tree[id << 1 | 1].min);
	}

	void update_pos(int id, int tl, int tr, int pos, long long val) {
		if (tl == tr) {
			tree[id].min = val;
			tree[id].lazy = 0;
			return;
		}
		push(id);
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			update_pos(id << 1, tl, tm, pos, val);
		}
		else {
			update_pos(id << 1 | 1, tm + 1, tr, pos, val);
		}
		merge(id);
	}

	void update_range(int id, int tl, int tr, int ql, int qr, long long delta) {
		if (tl == ql && tr == qr) {
			shift(id, delta);
			return;
		}
		push(id);
		int tm = (tl + tr) >> 1;
		if (qr <= tm) {
			update_range(id << 1, tl, tm, ql, qr, delta);
		}
		else if (ql >= tm + 1) {
			update_range(id << 1 | 1, tm + 1, tr, ql, qr, delta);
		}
		else {
			update_range(id << 1, tl, tm, ql, tm, delta);
			update_range(id << 1 | 1, tm + 1, tr, tm + 1, qr, delta);
		}
		merge(id);
	}

	long long get_range(int id, int tl, int tr, int ql, int qr) {
		if (tl == ql && tr == qr) {
			return tree[id].min;
		}
		push(id);
		int tm = (tl + tr) >> 1;
		if (qr <= tm) {
			return get_range(id << 1, tl, tm, ql, qr);
		}
		else if (ql >= tm + 1) {
			return get_range(id << 1 | 1, tm + 1, tr, ql, qr);
		}
		else {
			return min(get_range(id << 1, tl, tm, ql, tm), get_range(id << 1 | 1, tm + 1, tr, tm + 1, qr));
		}
	}

	void update_pos(int pos, long long val) {
		pos++;
		update_pos(1, 1, N, pos, val);
	}

	void update_pref(int r, long long delta) {
		if (r < 0) {
			return;
		}
		r++;
		update_range(1, 1, N, 1, r, delta);
	}

	long long get_pref(int r) {
		if (r < 0) {
			return inf2;
		}
		r++;
		return min(get_range(1, 1, N, 1, r), inf2);
	}
};

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]);
	}
	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<bool> is_heavy(planet_cnt);
	vector<int> heavy;
	vector<segment_tree> seg(planet_cnt);
	for (int i = 0; i < planet_cnt; i++) {
		int sz = planets[i].R - planets[i].L + 1;
		if (sz > lim) {
			is_heavy[i] = true;
			heavy.push_back(i);
			seg[i].init(sz);
		}
	}
	for (auto &t: trains) {
		t.low = lower_bound(meals.begin(), meals.end(), t.R) - meals.begin() - 1;
	}
	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;
				if (is_heavy[u]) {
					int pos = lower_bound(trains.begin() + planets[u].L, trains.begin() + planets[u].R + 1, trains[id].L) - trains.begin() - 1 - planets[u].L;
					dp[id] = min(seg[u].get_pref(pos) + trains[id].cost, inf2);
				}
				else {
					for (int i = planets[u].L; i <= planets[u].R; i++) {
						if (trains[i].R > trains[id].L) {
							break;
						}
						dp[id] = min(dp[id], dp[i] + planets[u].cost * fen.get(trains[i].low) + trains[id].cost);
					}
				}
			}
			int v = trains[id].v;
			if (is_heavy[v]) {
				seg[v].update_pos(id - planets[v].L, dp[id]);
			}
		}
		else {
			fen.update(id);
			for (auto u: heavy) {
				int pos = lower_bound(trains.begin() + planets[u].L, trains.begin() + planets[u].R + 1, meals[id].L - 1) - trains.begin() - 1 - planets[u].L;
				seg[u].update_pref(pos, planets[u].cost);
			}
		}
	}
	long long res = dp.back();
	if (res == inf2) {
		res = -1;
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 1 ms 344 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11072 KB Correct.
2 Correct 70 ms 15680 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 11 ms 5832 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 65 ms 10204 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 81 ms 21760 KB Correct.
9 Correct 76 ms 15664 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11072 KB Correct.
2 Correct 70 ms 15680 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 11 ms 5832 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 65 ms 10204 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 81 ms 21760 KB Correct.
9 Correct 76 ms 15664 KB Correct.
10 Correct 99 ms 16704 KB Correct.
11 Correct 110 ms 22080 KB Correct.
12 Correct 13 ms 5836 KB Correct.
13 Correct 0 ms 344 KB Correct.
14 Correct 217 ms 20084 KB Correct.
15 Correct 104 ms 22404 KB Correct.
16 Correct 714 ms 16068 KB Correct.
17 Correct 112 ms 27800 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 1 ms 344 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 62 ms 11072 KB Correct.
9 Correct 70 ms 15680 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 11 ms 5832 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 65 ms 10204 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 81 ms 21760 KB Correct.
16 Correct 76 ms 15664 KB Correct.
17 Correct 99 ms 16704 KB Correct.
18 Correct 110 ms 22080 KB Correct.
19 Correct 13 ms 5836 KB Correct.
20 Correct 0 ms 344 KB Correct.
21 Correct 217 ms 20084 KB Correct.
22 Correct 104 ms 22404 KB Correct.
23 Correct 714 ms 16068 KB Correct.
24 Correct 112 ms 27800 KB Correct.
25 Correct 113 ms 20964 KB Correct.
26 Correct 129 ms 22080 KB Correct.
27 Correct 111 ms 21740 KB Correct.
28 Correct 107 ms 20800 KB Correct.
29 Correct 103 ms 15748 KB Correct.
30 Correct 164 ms 15820 KB Correct.
31 Correct 163 ms 15808 KB Correct.
32 Correct 165 ms 17084 KB Correct.
33 Correct 266 ms 19868 KB Correct.
34 Correct 256 ms 19640 KB Correct.
35 Correct 255 ms 20412 KB Correct.
36 Correct 166 ms 16332 KB Correct.
37 Correct 110 ms 22336 KB Correct.
38 Correct 343 ms 15324 KB Correct.
39 Correct 155 ms 21736 KB Correct.
40 Correct 109 ms 20800 KB Correct.
41 Correct 102 ms 21056 KB Correct.
42 Correct 104 ms 15768 KB Correct.
43 Correct 153 ms 15364 KB Correct.
44 Correct 112 ms 22080 KB Correct.
45 Correct 107 ms 20796 KB Correct.
46 Correct 114 ms 21052 KB Correct.
47 Correct 96 ms 27204 KB Correct.
48 Correct 104 ms 28224 KB Correct.
49 Correct 132 ms 27204 KB Correct.
50 Correct 101 ms 27204 KB Correct.
51 Correct 100 ms 27100 KB Correct.
52 Correct 102 ms 27204 KB Correct.