oj.uz

Submission #991445

# Submission time Handle Problem Language Result Execution time Memory
991445 2024-06-02T09:13:39 Z SanguineChameleon Train (APIO24_train) C++17
10 / 100
 1000 ms 24168 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
const int lim = 300;
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;

	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): 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 {
	int sum[maxN];
	int N;

	fenwick_tree(int _N) {
		N = _N;
		for (int i = 1; i <= N; i++) {
			sum[i] = 0;
		}
	}

	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) {};
	};

	node tree[maxN << 2];
	int N;

	segment_tree(int _N) {
		N = _N;
	}

	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);
		}
	}
	vector<long long> dp(train_cnt, inf2);
	fenwick_tree fen(meal_cnt);
	segment_tree seg(train_cnt);
	int calls_cnt = 0;
	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;
						}
						calls_cnt++;
						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);
					}
				}
			}
			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 4 ms 7000 KB Correct.
2 Correct 4 ms 7004 KB Correct.
3 Correct 4 ms 7004 KB Correct.
4 Correct 3 ms 7004 KB Correct.
5 Correct 4 ms 7000 KB Correct.
6 Correct 3 ms 6900 KB Correct.
7 Correct 3 ms 7004 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16244 KB Correct.
2 Correct 66 ms 18264 KB Correct.
3 Correct 4 ms 7000 KB Correct.
4 Correct 12 ms 9936 KB Correct.
5 Correct 3 ms 7044 KB Correct.
6 Correct 63 ms 16760 KB Correct.
7 Correct 3 ms 7004 KB Correct.
8 Correct 61 ms 18428 KB Correct.
9 Correct 63 ms 18880 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16244 KB Correct.
2 Correct 66 ms 18264 KB Correct.
3 Correct 4 ms 7000 KB Correct.
4 Correct 12 ms 9936 KB Correct.
5 Correct 3 ms 7044 KB Correct.
6 Correct 63 ms 16760 KB Correct.
7 Correct 3 ms 7004 KB Correct.
8 Correct 61 ms 18428 KB Correct.
9 Correct 63 ms 18880 KB Correct.
10 Correct 150 ms 21872 KB Correct.
11 Correct 100 ms 24168 KB Correct.
12 Correct 11 ms 9936 KB Correct.
13 Correct 3 ms 7004 KB Correct.
14 Correct 280 ms 21460 KB Correct.
15 Correct 101 ms 23684 KB Correct.
16 Execution timed out 1060 ms 21700 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7000 KB Correct.
2 Correct 4 ms 7004 KB Correct.
3 Correct 4 ms 7004 KB Correct.
4 Correct 3 ms 7004 KB Correct.
5 Correct 4 ms 7000 KB Correct.
6 Correct 3 ms 6900 KB Correct.
7 Correct 3 ms 7004 KB Correct.
8 Correct 58 ms 16244 KB Correct.
9 Correct 66 ms 18264 KB Correct.
10 Correct 4 ms 7000 KB Correct.
11 Correct 12 ms 9936 KB Correct.
12 Correct 3 ms 7044 KB Correct.
13 Correct 63 ms 16760 KB Correct.
14 Correct 3 ms 7004 KB Correct.
15 Correct 61 ms 18428 KB Correct.
16 Correct 63 ms 18880 KB Correct.
17 Correct 150 ms 21872 KB Correct.
18 Correct 100 ms 24168 KB Correct.
19 Correct 11 ms 9936 KB Correct.
20 Correct 3 ms 7004 KB Correct.
21 Correct 280 ms 21460 KB Correct.
22 Correct 101 ms 23684 KB Correct.
23 Execution timed out 1060 ms 21700 KB Time limit exceeded
24 Halted 0 ms 0 KB -