oj.uz

Submission #993586

# Submission time Handle Problem Language Result Execution time Memory
993586 2024-06-06T05:38:44 Z green_gold_dog Train (APIO24_train) C++17
40 / 100
 334 ms 93276 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();
}

#ifdef LOCAL
signed main() {
  int N, M, W;
  assert(3 == scanf("%d %d %d", &N, &M, &W));
  std::vector<int> t(N);
  std::vector<int> x(M);
  std::vector<int> y(M);
  std::vector<int> a(M);
  std::vector<int> b(M);
  std::vector<int> c(M);
  std::vector<int> l(W);
  std::vector<int> r(W);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &t[i]));
  for (int i = 0; i < M; i++)
    assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
  for (int i = 0; i < W; i++)
    assert(2 == scanf("%d %d", &l[i], &r[i]));
  printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4044 KB Correct.
2 Correct 141 ms 11860 KB Correct.
3 Correct 142 ms 5196 KB Correct.
4 Correct 137 ms 4432 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 70 ms 17028 KB Correct.
2 Correct 149 ms 77140 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 37 ms 66876 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 65 ms 11104 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 92 ms 77032 KB Correct.
9 Correct 127 ms 77028 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 17028 KB Correct.
2 Correct 149 ms 77140 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 37 ms 66876 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 65 ms 11104 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 92 ms 77032 KB Correct.
9 Correct 127 ms 77028 KB Correct.
10 Correct 231 ms 33220 KB Correct.
11 Correct 251 ms 93124 KB Correct.
12 Correct 39 ms 66900 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 233 ms 26840 KB Correct.
15 Correct 267 ms 93016 KB Correct.
16 Correct 202 ms 26592 KB Correct.
17 Correct 165 ms 93124 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4044 KB Correct.
2 Correct 141 ms 11860 KB Correct.
3 Correct 142 ms 5196 KB Correct.
4 Correct 137 ms 4432 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 70 ms 17028 KB Correct.
9 Correct 149 ms 77140 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 37 ms 66876 KB Correct.
12 Correct 1 ms 344 KB Correct.
13 Correct 65 ms 11104 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 92 ms 77032 KB Correct.
16 Correct 127 ms 77028 KB Correct.
17 Correct 231 ms 33220 KB Correct.
18 Correct 251 ms 93124 KB Correct.
19 Correct 39 ms 66900 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 233 ms 26840 KB Correct.
22 Correct 267 ms 93016 KB Correct.
23 Correct 202 ms 26592 KB Correct.
24 Correct 165 ms 93124 KB Correct.
25 Correct 286 ms 93068 KB Correct.
26 Correct 299 ms 93124 KB Correct.
27 Correct 334 ms 93124 KB Correct.
28 Correct 326 ms 93276 KB Correct.
29 Correct 230 ms 33220 KB Correct.
30 Incorrect 247 ms 27340 KB Wrong Answer.
31 Halted 0 ms 0 KB -