oj.uz

Submission #997942

# Submission time Handle Problem Language Result Execution time Memory
997942 2024-06-13T07:03:57 Z Trisanu_Das Train (APIO24_train) C++17
40 / 100
 297 ms 93132 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const long long INF = 1'000'000'000'000'000;
const ll INF32 = 1'000'000'001;
 
void upd(ll w, vector<long long>& all, ll c, ll nw, vector<pair<ll, ll>>& eat) {
	for (ll i = 0; i < (1 << w); i++) {
		bool b = false;
		for (ll j = 0; j < w; j++) {
			if (!((i >> j) & 1)) {
				if (eat[j].first <= nw) all[i + (1 << j)] = min(all[i] + c, all[i + (1 << j)]);
				if (eat[j].second < nw) b = true;
			}
		}
		if (b) all[i] = INF;
	}
}
 
struct BIT {
	vector<ll> tree;
	vector<ll> all;
	BIT(vector<ll> a) {
		all = a;
		all.push_back(-1);
		all.push_back(INF32);
		sort(all.begin(), all.end());
		tree.resize(all.size() + 1);
	}
	ll s(ll x) {
		return lower_bound(all.begin(), all.end(), x) - all.begin();
	}
	void add(ll x) {
		x = s(x);
		x++;
		for (; x < tree.size(); x += x & -x) tree[x]++;
	}
	ll get(ll l, ll r) {
		return get(r) - get(l);
	}
	ll get(ll x) {
		x = s(x);
		ll ans = 0;
		for (; x > 0; x -= x & -x) ans += tree[x];
		return ans;
	}
};
 
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) {
	if (W <= 10 && N <= 1000 && M <= 1000) {
		vector<pair<ll, ll>> eat;
		multiset<tuple<ll, ll, ll, long long, ll>> s;
		for (ll i = 0; i < W; i++) eat.emplace_back(L[i], R[i]);
		sort(eat.begin(), eat.end());
		vector<vector<long long>> ans(N, vector<long long>(1 << W, INF));
		ans[0][0] = 0;
		for (ll i = 0; i < M; i++) s.emplace(A[i], 2, i, 0ll, 0);
		while (!s.empty()) {
			auto[nt, t, i, c, m] = *s.begin();
			s.erase(s.begin());
			if (t == 2) {
				upd(W, ans[X[i]], T[X[i]], nt, eat);
				ll nc = 0;
				for (ll j = 0; j < W; j++) if (eat[j].first <= B[i] && eat[j].second >= nt) nc += 1 << j;
				for (ll j = 0; j < (1 << W); j++) s.emplace(B[i], 1, i, C[i] + ans[X[i]][j], j | nc);
			} else ans[Y[i]][m] = min(ans[Y[i]][m], c);
		}
		upd(W, ans.back(), T.back(), INF32, eat);
		if (ans.back().back() >= INF) return -1;
		return ans.back().back();
	}
	vector<pair<ll, ll>> eat;
	multiset<tuple<ll, ll, ll, long long>> s;
	vector<ll> all;
	for (ll i = 0; i < W; i++) {
		eat.emplace_back(R[i], L[i]);
		s.emplace(R[i], 3, i, 0ll);
		s.emplace(L[i], 0, 0, 0ll);
		all.push_back(L[i]);
	}
	BIT bi(all);
	sort(eat.begin(), eat.end());
	vector<deque<pair<long long, pair<long long, long long>>>> nmaco(N);
	nmaco[0].emplace_back(0, make_pair(0, 0));
	for (ll i = 0; i < M; i++) s.emplace(A[i], 2, i, 0ll);
	long long co = 0, maco = 0;
	while (!s.empty()) {
		auto[_, t, i, c] = *s.begin();
		s.erase(s.begin());
		if (t == 0) {
			maco++;
			continue;
		}
		if (t == 3) {
			bi.add(L[i]);
			co++;
			continue;
		}
		if (t == 2) {
			if (nmaco[X[i]].empty()) continue;
			while (nmaco[X[i]].size() > 1 && nmaco[X[i]][0].first + (nmaco[X[i]][0].second.first + bi.get(nmaco[X[i]][0].second.second, INF32)) * T[X[i]] >= nmaco[X[i]][1].first + (nmaco[X[i]][1].second.first + bi.get(nmaco[X[i]][1].second.second, INF32)) * T[X[i]]) nmaco[X[i]].pop_front();
			s.emplace(B[i], 1, i, C[i] + nmaco[X[i]].front().first + (nmaco[X[i]].front().second.first + bi.get(nmaco[X[i]].front().second.second, INF32)) * T[X[i]]);
		} else {
			c -= maco * T[Y[i]];
			if (nmaco[Y[i]].empty() || nmaco[Y[i]].back().first > c) {
				while (!nmaco[Y[i]].empty() && nmaco[Y[i]].back().second.first == maco)  nmaco[Y[i]].pop_back();
				nmaco[Y[i]].emplace_back(c, make_pair(maco, B[i] + 1));
			}
		}
	}
	if (nmaco.back().empty()) return -1;
	while (nmaco.back().size() > 1 && nmaco.back()[0].first + (nmaco.back()[0].second.first + bi.get(nmaco.back()[0].second.second, INF32)) * T.back() >= nmaco.back()[1].first + (nmaco.back()[1].second.first + bi.get(nmaco.back()[1].second.second, INF32)) * T.back()) nmaco.back().pop_front();
	if (nmaco.back().front().first + co * T.back() >= INF) return -1;
	return nmaco.back().front().first + co * T.back();
}

Compilation message

train.cpp: In member function 'void BIT::add(ll)':
train.cpp:37:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (; x < tree.size(); x += x & -x) tree[x]++;
      |          ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4048 KB Correct.
2 Correct 139 ms 11864 KB Correct.
3 Correct 133 ms 5180 KB Correct.
4 Correct 129 ms 4432 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17264 KB Correct.
2 Correct 107 ms 77140 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 34 ms 66904 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 59 ms 11280 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 83 ms 77116 KB Correct.
9 Correct 118 ms 77140 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17264 KB Correct.
2 Correct 107 ms 77140 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 34 ms 66904 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 59 ms 11280 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 83 ms 77116 KB Correct.
9 Correct 118 ms 77140 KB Correct.
10 Correct 215 ms 33296 KB Correct.
11 Correct 246 ms 93024 KB Correct.
12 Correct 37 ms 66900 KB Correct.
13 Correct 1 ms 344 KB Correct.
14 Correct 182 ms 26584 KB Correct.
15 Correct 241 ms 93024 KB Correct.
16 Correct 178 ms 26568 KB Correct.
17 Correct 162 ms 93128 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4048 KB Correct.
2 Correct 139 ms 11864 KB Correct.
3 Correct 133 ms 5180 KB Correct.
4 Correct 129 ms 4432 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 64 ms 17264 KB Correct.
9 Correct 107 ms 77140 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Correct 34 ms 66904 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 59 ms 11280 KB Correct.
14 Correct 1 ms 344 KB Correct.
15 Correct 83 ms 77116 KB Correct.
16 Correct 118 ms 77140 KB Correct.
17 Correct 215 ms 33296 KB Correct.
18 Correct 246 ms 93024 KB Correct.
19 Correct 37 ms 66900 KB Correct.
20 Correct 1 ms 344 KB Correct.
21 Correct 182 ms 26584 KB Correct.
22 Correct 241 ms 93024 KB Correct.
23 Correct 178 ms 26568 KB Correct.
24 Correct 162 ms 93128 KB Correct.
25 Correct 256 ms 93132 KB Correct.
26 Correct 277 ms 93024 KB Correct.
27 Correct 291 ms 93032 KB Correct.
28 Correct 297 ms 93104 KB Correct.
29 Correct 221 ms 33284 KB Correct.
30 Incorrect 211 ms 27368 KB Wrong Answer.
31 Halted 0 ms 0 KB -