oj.uz

Submission #684733

# Submission time Handle Problem Language Result Execution time Memory
684733 2023-01-22T11:49:45 Z flappybird Golf (JOI17_golf) C++17
30 / 100
 1962 ms 511164 KB 
#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 201010
#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 * 2];
int hmx[MAX * 2];
int hmn[MAX * 2];
vector<int> hpoint[MAX * 2];
vector<pii> hline[MAX];
pii ver[MAX * 2];
int vmx[MAX * 2];
int vmn[MAX * 2];
vector<int> vpoint[MAX * 2];
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28628 KB Output is correct
3 Correct 15 ms 28592 KB Output is correct
4 Correct 15 ms 28884 KB Output is correct
5 Correct 20 ms 30200 KB Output is correct
6 Correct 21 ms 30228 KB Output is correct
7 Correct 23 ms 30152 KB Output is correct
8 Correct 23 ms 30220 KB Output is correct
9 Correct 21 ms 30312 KB Output is correct
10 Correct 21 ms 30220 KB Output is correct
11 Correct 23 ms 30292 KB Output is correct
12 Correct 21 ms 30220 KB Output is correct
13 Correct 23 ms 30284 KB Output is correct
14 Correct 24 ms 30224 KB Output is correct
15 Correct 18 ms 29524 KB Output is correct
16 Correct 22 ms 30432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28628 KB Output is correct
3 Correct 15 ms 28592 KB Output is correct
4 Correct 15 ms 28884 KB Output is correct
5 Correct 20 ms 30200 KB Output is correct
6 Correct 21 ms 30228 KB Output is correct
7 Correct 23 ms 30152 KB Output is correct
8 Correct 23 ms 30220 KB Output is correct
9 Correct 21 ms 30312 KB Output is correct
10 Correct 21 ms 30220 KB Output is correct
11 Correct 23 ms 30292 KB Output is correct
12 Correct 21 ms 30220 KB Output is correct
13 Correct 23 ms 30284 KB Output is correct
14 Correct 24 ms 30224 KB Output is correct
15 Correct 18 ms 29524 KB Output is correct
16 Correct 22 ms 30432 KB Output is correct
17 Correct 24 ms 31044 KB Output is correct
18 Correct 22 ms 30956 KB Output is correct
19 Correct 22 ms 31060 KB Output is correct
20 Correct 23 ms 31060 KB Output is correct
21 Correct 25 ms 31156 KB Output is correct
22 Correct 24 ms 31036 KB Output is correct
23 Correct 22 ms 31112 KB Output is correct
24 Correct 24 ms 31116 KB Output is correct
25 Correct 22 ms 30996 KB Output is correct
26 Correct 23 ms 31116 KB Output is correct
27 Correct 18 ms 29708 KB Output is correct
28 Correct 24 ms 30696 KB Output is correct
29 Correct 21 ms 30764 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28628 KB Output is correct
3 Correct 15 ms 28592 KB Output is correct
4 Correct 15 ms 28884 KB Output is correct
5 Correct 20 ms 30200 KB Output is correct
6 Correct 21 ms 30228 KB Output is correct
7 Correct 23 ms 30152 KB Output is correct
8 Correct 23 ms 30220 KB Output is correct
9 Correct 21 ms 30312 KB Output is correct
10 Correct 21 ms 30220 KB Output is correct
11 Correct 23 ms 30292 KB Output is correct
12 Correct 21 ms 30220 KB Output is correct
13 Correct 23 ms 30284 KB Output is correct
14 Correct 24 ms 30224 KB Output is correct
15 Correct 18 ms 29524 KB Output is correct
16 Correct 22 ms 30432 KB Output is correct
17 Correct 24 ms 31044 KB Output is correct
18 Correct 22 ms 30956 KB Output is correct
19 Correct 22 ms 31060 KB Output is correct
20 Correct 23 ms 31060 KB Output is correct
21 Correct 25 ms 31156 KB Output is correct
22 Correct 24 ms 31036 KB Output is correct
23 Correct 22 ms 31112 KB Output is correct
24 Correct 24 ms 31116 KB Output is correct
25 Correct 22 ms 30996 KB Output is correct
26 Correct 23 ms 31116 KB Output is correct
27 Correct 18 ms 29708 KB Output is correct
28 Correct 24 ms 30696 KB Output is correct
29 Correct 21 ms 30764 KB Output is correct
30 Runtime error 1962 ms 511164 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -