oj.uz

Submission #991493

# Submission time Handle Problem Language Result Execution time Memory
991493 2024-06-02T10:15:15 Z SanguineChameleon Train (APIO24_train) C++17
100 / 100
 735 ms 25664 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;

	segment_tree(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_range(int l, int r, long long delta) {
		if (l > r) {
			return;
		}
		l++;
		r++;
		update_range(1, 1, N, l, r, delta);
	}

	long long get_range(int l, int r) {
		if (l > r) {
			return inf2;
		}
		l++;
		r++;
		return min(get_range(1, 1, N, l, 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);
	for (int i = 0; i < planet_cnt; i++) {
		is_heavy[i] = (planets[i].R - planets[i].L + 1) > lim;
	}
	vector<int> heavy;
	for (int i = 0; i < planet_cnt; i++) {
		if (is_heavy[i]) {
			heavy.push_back(i);
		}
	}
	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);
	segment_tree seg(train_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;
					dp[id] = min(seg.get_range(planets[u].L, 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.update_pos(id, 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;
				seg.update_range(planets[u].L, 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 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 600 KB Correct.
7 Correct 0 ms 344 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16500 KB Correct.
2 Correct 70 ms 19200 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 9 ms 3252 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 61 ms 16348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 76 ms 18752 KB Correct.
9 Correct 61 ms 18756 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16500 KB Correct.
2 Correct 70 ms 19200 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 9 ms 3252 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 61 ms 16348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 76 ms 18752 KB Correct.
9 Correct 61 ms 18756 KB Correct.
10 Correct 97 ms 21816 KB Correct.
11 Correct 103 ms 24636 KB Correct.
12 Correct 9 ms 3280 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 301 ms 22216 KB Correct.
15 Correct 99 ms 25664 KB Correct.
16 Correct 735 ms 21976 KB Correct.
17 Correct 129 ms 24128 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 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 600 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 58 ms 16500 KB Correct.
9 Correct 70 ms 19200 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 9 ms 3252 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 61 ms 16348 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 76 ms 18752 KB Correct.
16 Correct 61 ms 18756 KB Correct.
17 Correct 97 ms 21816 KB Correct.
18 Correct 103 ms 24636 KB Correct.
19 Correct 9 ms 3280 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 301 ms 22216 KB Correct.
22 Correct 99 ms 25664 KB Correct.
23 Correct 735 ms 21976 KB Correct.
24 Correct 129 ms 24128 KB Correct.
25 Correct 105 ms 24040 KB Correct.
26 Correct 102 ms 24300 KB Correct.
27 Correct 108 ms 24128 KB Correct.
28 Correct 103 ms 25304 KB Correct.
29 Correct 101 ms 22584 KB Correct.
30 Correct 157 ms 21728 KB Correct.
31 Correct 156 ms 21692 KB Correct.
32 Correct 156 ms 22280 KB Correct.
33 Correct 365 ms 21948 KB Correct.
34 Correct 388 ms 21792 KB Correct.
35 Correct 364 ms 21724 KB Correct.
36 Correct 171 ms 21692 KB Correct.
37 Correct 105 ms 24128 KB Correct.
38 Correct 345 ms 21696 KB Correct.
39 Correct 176 ms 21692 KB Correct.
40 Correct 103 ms 24128 KB Correct.
41 Correct 98 ms 25404 KB Correct.
42 Correct 94 ms 22844 KB Correct.
43 Correct 145 ms 22284 KB Correct.
44 Correct 105 ms 25152 KB Correct.
45 Correct 104 ms 24128 KB Correct.
46 Correct 103 ms 24128 KB Correct.
47 Correct 115 ms 24128 KB Correct.
48 Correct 111 ms 25052 KB Correct.
49 Correct 143 ms 24132 KB Correct.
50 Correct 112 ms 24100 KB Correct.
51 Correct 116 ms 24900 KB Correct.
52 Correct 145 ms 25412 KB Correct.