Submission #997942

#	Time	Username	Problem	Language	Result	Execution time	Memory
997942		Trisanu_Das	은하철도 (APIO24_train)	C++17	40 / 100	297 ms	93132 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();
}

Compilation message (stderr)

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