Submission #802088

#	Time	Username	Problem	Language	Result	Execution time	Memory
802088		flappybird	Cultivation (JOI17_cultivation)	C++17	80 / 100	1909 ms	12748 KiB

cultivation

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 20
#define INF 2000000000000020
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
ll H, W;
int N;
pii arr[MAX];
ll ans = 2e9;
vector<int> st[MAX], en[MAX];
int U[MAX], D[MAX], UD[MAX];
deque<pii> up, down, su;
bool test(ll d) {
	if (d <= 0) return false;
	vector<ll> ys;
	int i, j;
	for (i = 1; i <= N; i++) ys.push_back(arr[i].second), ys.push_back(arr[i].second + d);
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	int X = ys.size();
	multiset<int> ds, alls;
	for (i = 0; i < X; i++) U[i] = D[i] = UD[i] = 0, st[i].clear(), en[i].clear();
	for (i = 1; i <= N; i++) {
		int l, r;
		l = lower_bound(ys.begin(), ys.end(), arr[i].second) - ys.begin();
		r = lower_bound(ys.begin(), ys.end(), arr[i].second + d) - ys.begin();
		st[l].push_back(i);
		en[r].push_back(i);
	}
	for (i = 0; i < X; i++) {
		for (auto v : st[i]) {
			int x = arr[v].first;
			if (alls.size() && alls.find(x) == alls.end()) {
				auto it = alls.lower_bound(x);
				if (it == alls.end()) ds.insert(x - *(--it) - 1);
				else if (it == alls.begin()) ds.insert(*it - x - 1);
				else {
					int ne = *it;
					it--;
					int pv = *it;
					ds.erase(ds.find(ne - pv - 1));
					ds.insert(ne - x - 1);
					ds.insert(x - pv - 1);
				}
			}
			alls.insert(x);
		}
		for (auto v : en[i]) {
			int x = arr[v].first;
			alls.erase(alls.find(x));
			if (alls.size() && alls.find(x) == alls.end()) {
				auto it = alls.lower_bound(x);
				if (it == alls.end()) ds.erase(ds.find(x - *(--it) - 1));
				else if (it == alls.begin()) ds.erase(ds.find(*it - x - 1));
				else {
					ll ne = *it;
					it--;
					ll pv = *it;
					ds.insert(ne - pv - 1);
					ds.erase(ds.find(ne - x - 1));
					ds.erase(ds.find(x - pv - 1));
				}
			}
		}
		if (ds.size()) UD[i] = *ds.rbegin();
		if (alls.empty()) UD[i] = 2e9;
		else {
			U[i] = *alls.begin() - 1;
			D[i] = H - *alls.rbegin();
		}
	}
	up.clear();
	down.clear();
	su.clear();
	ll mn = INF;
	j = 0;
	for (i = 0; i < X - 1; i++) {
		while (up.size() && up.back().first <= U[i]) up.pop_back();
		up.emplace_back(U[i], i);
		while (down.size() && down.back().first <= D[i]) down.pop_back();
		down.emplace_back(D[i], i);
		while (su.size() && su.back().first <= UD[i]) su.pop_back();
		su.emplace_back(UD[i], i);
		while (j + 1 <= i && ys[i + 1] - ys[j + 1] >= W) j++;
		while (up.size() && up.front().second < j) up.pop_front();
		while (down.size() && down.front().second < j) down.pop_front();
		while (su.size() && su.front().second < j) su.pop_front();
		if (ys[i + 1] - ys[j] >= W) mn = min(mn, max(0ll + up.front().first + down.front().first, (ll)su.front().first));
	}
	if (mn >= INF) return false;
	ans = min(ans, mn + d - 1);
	return true;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	clock_t start, finish;
	cin >> H >> W >> N;
	start = clock();
	swap(H, W);
	int i, j;
	vector<ll> ls;
	ls.push_back(W);
	for (i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second, swap(arr[i].first, arr[i].second);
	for (i = 1; i <= N; i++) {
		for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second));
		for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second) + W);
		ls.push_back(arr[i].second);
		ls.push_back(W - arr[i].second + 1);
	}
	vector<ll> cpy;
	for (auto v : ls) cpy.push_back(W - v);
	for (auto v : cpy) ls.push_back(v);
	sort(ls.begin(), ls.end());
	ls.erase(unique(ls.begin(), ls.end()), ls.end());
	reverse(ls.begin(), ls.end());
	while (ls.back() <= 0) ls.pop_back();
	for (i = (int)ls.size() - 1; i >= 0; i--) swap(ls[i], ls[rand() % (i + 1)]);
	ll mv = 0;
	int rot = 100;
	for (auto v : ls) {
		if (v < mv) continue;
		if (!test(v)) mv = max(mv, v);
		rot--;
		if (!rot) {
			rot = 100;
			finish = clock();
			auto duration = (double)(finish - start) / (double)CLOCKS_PER_SEC;
			if (duration > 1.9) break;
		}
	}
	cout << ans << ln;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 0 / 20