Submission #556919

#	Time	Username	Problem	Language	Result	Execution time	Memory
556919		DanShaders	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	302 ms	22336 KiB

kyoto

//bs:sanitizers
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

#define int ll

const int N = 1e5 + 10, M = 2010, INF = 0x3f3f3f3f3f3f3f3f;

int a[2][N], where[2][N];
list<int> c[2];

int version[2][N];

struct Entry {
	ld fitness;

	int x, y, ver;
	list<int>::iterator it;

	bool operator<(const Entry &other) const {
		return fitness < other.fitness;
	}
};

priority_queue<Entry> q;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n[2];
	cin >> n[0] >> n[1];
	
	for (int j = 0; j < 2; ++j) {
		for (int i = 0; i < n[j]; ++i) {
			cin >> a[j][i];
		}
		for (int i = 0; i < n[j] - 1; ++i) {
			c[j].push_back(i);
			q.push({ld(a[j][i] - a[j][i + 1]), j, i, 0, prev(c[j].end())});
		}
		c[j].push_back(n[j] - 1);
	}

	for (int iter = 1; sz(q); ++iter) {
		auto [fitness, x, y, ver, it] = q.top();
		// cout << "using " << fitness << " " << x << " " << y << endl;
		q.pop();
		if (version[x][y] != ver) {
			continue;
		}
		where[x][y] = iter;
		// cout << sz(c[x]) << endl;
		if (it != c[x].begin() && sz(c[x]) > 2) {
			// cout << "recount delta" << endl;
			auto prv = prev(it), nxt = next(it);
			version[x][*prv] = iter;
			q.push({(a[x][*prv] - a[x][*nxt]) / ld(*nxt - *prv), x, *prv, iter, prv});
		}
		// cout << "removing " << x << " " << *it << endl;
		c[x].erase(it);
	}

	ll ans = 0;
	int cx = 0, cy = 0;
	for (int i = 0; i < n[0] + n[1] - 2; ++i) {
		// cout << cx << " " << cy << endl;
		if (cx != n[0] - 1 && (cy == n[1] - 1 || where[0][cx] < where[1][cy])) {
			ans += a[1][cy];
			++cx;
		} else {
			ans += a[0][cx];
			++cy;
		}
	}
	// cout << cx << " " << cy << endl;
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60