Submission #684734

#	Time	Username	Problem	Language	Result	Execution time	Memory
684734		flappybird	Golf (JOI17_golf)	C++17	100 / 100	2882 ms	521944 KiB

golf

#include <bits/stdc++.h>
#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 801010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<pii, pii> T;
T points[MAX];
int getind(vector<int>& v, int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin();
}
pii hor[MAX];
int hmx[MAX];
int hmn[MAX];
vector<int> hpoint[MAX];
vector<pii> hline[MAX];
pii ver[MAX];
int vmx[MAX];
int vmn[MAX];
vector<int> vpoint[MAX];
vector<pii> vline[MAX];
int dist[MAX];
struct segtree {
	vector<set<pii>> tree;
	int N;
	segtree(int N) :N(N) { tree.resize(N * 4 + 10); }
	void upd(int s, int e, int l, int r, pii x, int loc = 1) {
		if (e < l || r < s) return;
		if (l <= s && e <= r) {
			tree[loc].insert(x);
			return;
		}
		int m = (s + e) >> 1;
		upd(s, m, l, r, x, loc * 2);
		upd(m + 1, e, l, r, x, loc * 2 + 1);
	}
	void addq(int s, int e, int x, int mn, int mx, vector<int>& q, int loc = 1) {
		if (e < x || x < s) return;
		while (1) {
			auto it = tree[loc].lower_bound(pii(mn, -1));
			if (it == tree[loc].end()) break;
			if (it->first > mx) break;
			q.push_back(it->second);
			tree[loc].erase(it);
		}
		if (s == e) return;
		int m = (s + e) >> 1;
		addq(s, m, x, mn, mx, q, loc * 2);
		addq(m + 1, e, x, mn, mx, q, loc * 2 + 1);
	}
	void upd(int l, int r, pii x) { upd(0, N, l, r, x); }
	void addq(int x, int mn, int mx, vector<int>& q) { addq(0, N, x, mn, mx, q); }
};
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	cin >> N;
	int i;
	vector<int> Xs, Ys;
	for (i = 1; i <= N; i++) {
		cin >> points[i].first.first >> points[i].second.first >> points[i].first.second >> points[i].second.second;
		Xs.push_back(points[i].first.first);
		Xs.push_back(points[i].second.first);
		Ys.push_back(points[i].first.second);
		Ys.push_back(points[i].second.second);
	}
	Xs.push_back(sx);
	Xs.push_back(ex);
	Ys.push_back(sy);
	Ys.push_back(ey);
	Xs.push_back(0);
	Ys.push_back(0);
	Xs.push_back(1000000001);
	Ys.push_back(1000000001);
	sort(Xs.begin(), Xs.end());
	sort(Ys.begin(), Ys.end());
	Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());
	Ys.erase(unique(Ys.begin(), Ys.end()), Ys.end());
	int H, W;
	H = Ys.size();
	W = Xs.size();
	sx = getind(Xs, sx);
	ex = getind(Xs, ex);
	sy = getind(Ys, sy);
	ey = getind(Ys, ey);
	for (i = 1; i <= N; i++) {
		points[i].first.first = getind(Xs, points[i].first.first);
		points[i].second.first = getind(Xs, points[i].second.first);
		points[i].first.second = getind(Ys, points[i].first.second);
		points[i].second.second = getind(Ys, points[i].second.second);
	}
	int HS, VS;
	int cnt;
	cnt = 0;
	hor[++cnt] = pii(sx, sy);
	hor[++cnt] = pii(ex, ey);
	for (i = 1; i <= N; i++) hor[++cnt] = points[i].first, hor[++cnt] = points[i].second;
	for (i = 1; i <= cnt; i++) hpoint[hor[i].first].push_back(i);
	for (i = 1; i <= N; i++) hline[points[i].first.first].emplace_back(points[i].first.second, points[i].second.second), hline[points[i].second.first].emplace_back(points[i].first.second, points[i].second.second);
	set<pii> st;
	for (i = 0; i < W; i++) {
		for (auto v : hpoint[i]) st.emplace(hor[v].second, v);
		for (auto& [l, r] : hline[i]) {
			while (1) {
				auto it = st.upper_bound(pii(l, 1e9));
				if (it == st.end()) break;
				if (hor[it->second].second >= r) break;
				else {
					hmx[it->second] = i;
					st.erase(it);
				}
			}
		}
	}
	for (auto& [_, v] : st) hmx[v] = W - 1;
	st.clear();
	for (i = W - 1; i >= 0; i--) {
		for (auto v : hpoint[i]) st.emplace(hor[v].second, v);
		for (auto& [l, r] : hline[i]) {
			while (1) {
				auto it = st.upper_bound(pii(l, 1e9));
				if (it == st.end()) break;
				if (hor[it->second].second >= r) break;
				else {
					hmn[it->second] = i;
					st.erase(it);
				}
			}
		}
	}
	for (auto& [_, v] : st) hmn[v] = 0;
	st.clear();
	HS = cnt;
	segtree hors(W + 1);
	for (i = 2; i <= cnt; i++) hors.upd(hmn[i], hmx[i], pii(hor[i].second, i));
	cnt = 0;
	ver[++cnt] = pii(sx, sy);
	ver[++cnt] = pii(ex, ey);
	for (i = 1; i <= N; i++) ver[++cnt] = points[i].first, ver[++cnt] = points[i].second;
	for (i = 1; i <= cnt; i++) vpoint[ver[i].second].push_back(i);
	for (i = 1; i <= N; i++) vline[points[i].first.second].emplace_back(points[i].first.first, points[i].second.first), vline[points[i].second.second].emplace_back(points[i].first.first, points[i].second.first);
	for (i = 0; i < H; i++) {
		for (auto v : vpoint[i]) st.emplace(ver[v].first, v);
		for (auto& [l, r] : vline[i]) {
			while (1) {
				auto it = st.upper_bound(pii(l, 1e9));
				if (it == st.end()) break;
				if (ver[it->second].first >= r) break;
				else {
					vmx[it->second] = i;
					st.erase(it);
				}
			}
		}
	}
	for (auto& [_, v] : st) vmx[v] = H - 1;
	st.clear();
	for (i = H - 1; i >= 0; i--) {
		for (auto v : vpoint[i]) st.emplace(hor[v].first, v);
		for (auto& [l, r] : vline[i]) {
			while (1) {
				auto it = st.upper_bound(pii(l, 1e9));
				if (it == st.end()) break;
				if (ver[it->second].first >= r) break;
				else {
					vmn[it->second] = i;
					st.erase(it);
				}
			}
		}
	}
	for (auto& [_, v] : st) vmn[v] = 0;
	VS = cnt;
	segtree vers(H + 1);
	for (i = 2; i <= cnt; i++) vers.upd(vmn[i], vmx[i], pii(ver[i].first, i + HS));
	if (sy == ey) {
		if (ex <= hmx[1]) {
			cout << 1 << ln;
			return 0;
		}
	}
	if (sx == ex) {
		if (ey <= vmx[1]) {
			cout << 1 << ln;
			return 0;
		}
	}
	queue<int> q;
	q.push(1);
	q.push(HS + 1);
	vector<int> nxt;
	dist[1] = dist[HS + 1] = 1;
	while (q.size()) {
		int t = q.front();
		q.pop();
		if (t == HS + 2 || t == 2) {
			cout << dist[t] << ln;
			return 0;
		}
		if (t > HS) hors.addq(ver[t - HS].first, vmn[t - HS], vmx[t - HS], nxt);
		else vers.addq(hor[t].second, hmn[t], hmx[t], nxt);
		for (auto v : nxt) if (!dist[v]) dist[v] = dist[t] + 1, q.push(v);
		nxt.clear();
	}
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:103:10: warning: variable 'VS' set but not used [-Wunused-but-set-variable]
  103 |  int HS, VS;
      |          ^~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70