oj.uz

Submission #991491

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

const int lim = 1000;
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 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 344 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 56 ms 10196 KB Correct.
2 Correct 62 ms 15688 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 10 ms 5836 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 61 ms 11128 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 57 ms 22492 KB Correct.
9 Correct 65 ms 15936 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10196 KB Correct.
2 Correct 62 ms 15688 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 10 ms 5836 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 61 ms 11128 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 57 ms 22492 KB Correct.
9 Correct 65 ms 15936 KB Correct.
10 Correct 98 ms 15680 KB Correct.
11 Correct 103 ms 21020 KB Correct.
12 Correct 10 ms 5836 KB Correct.
13 Correct 0 ms 344 KB Correct.
14 Correct 197 ms 20956 KB Correct.
15 Correct 101 ms 20800 KB Correct.
16 Correct 969 ms 18104 KB Correct.
17 Correct 105 ms 27200 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 56 ms 10196 KB Correct.
9 Correct 62 ms 15688 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Correct 10 ms 5836 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 61 ms 11128 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 57 ms 22492 KB Correct.
16 Correct 65 ms 15936 KB Correct.
17 Correct 98 ms 15680 KB Correct.
18 Correct 103 ms 21020 KB Correct.
19 Correct 10 ms 5836 KB Correct.
20 Correct 0 ms 344 KB Correct.
21 Correct 197 ms 20956 KB Correct.
22 Correct 101 ms 20800 KB Correct.
23 Correct 969 ms 18104 KB Correct.
24 Correct 105 ms 27200 KB Correct.
25 Correct 106 ms 20952 KB Correct.
26 Correct 107 ms 21256 KB Correct.
27 Correct 106 ms 20804 KB Correct.
28 Correct 113 ms 21720 KB Correct.
29 Correct 103 ms 15936 KB Correct.
30 Correct 162 ms 15804 KB Correct.
31 Correct 160 ms 15548 KB Correct.
32 Correct 163 ms 15552 KB Correct.
33 Correct 248 ms 19644 KB Correct.
34 Correct 252 ms 19836 KB Correct.
35 Correct 265 ms 20152 KB Correct.
36 Correct 168 ms 16060 KB Correct.
37 Correct 107 ms 20800 KB Correct.
38 Correct 351 ms 16576 KB Correct.
39 Correct 137 ms 21720 KB Correct.
40 Correct 131 ms 20796 KB Correct.
41 Correct 101 ms 20800 KB Correct.
42 Correct 96 ms 15680 KB Correct.
43 Correct 142 ms 15328 KB Correct.
44 Correct 110 ms 21020 KB Correct.
45 Correct 133 ms 20800 KB Correct.
46 Correct 105 ms 20800 KB Correct.
47 Correct 95 ms 27204 KB Correct.
48 Correct 100 ms 27204 KB Correct.
49 Correct 94 ms 28652 KB Correct.
50 Correct 99 ms 27200 KB Correct.
51 Correct 94 ms 27112 KB Correct.
52 Correct 93 ms 28480 KB Correct.