Submission #993586

#	Time	Username	Problem	Language	Result	Execution time	Memory
993586		green_gold_dog	Train (APIO24_train)	C++17	40 / 100	334 ms	93276 KiB

train

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60