Submission #171534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171534	2019-12-29T04:59:44 Z	youngyojun	Sky Walking (IOI19_walk)	C++17	100 / 100	2073 ms	134904 KB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define fi first
#define se second
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

const int MAXN = 100055;
const int MAXM = 100055;
const int MAXK = 2000055;

struct EVT {
	EVT(int type, pii p)
		: type(type), p(p) {}
	int type;
	pii p;

	bool operator < (const EVT &t) const {
		if(p.fi != t.p.fi) return p.fi < t.p.fi;
		return type < t.type;
	}
};

vector<int> G[MAXK];
ll dp[MAXK];

vector<pii> PV;

int A[MAXN], B[MAXN];
int C[MAXM], D[MAXM], E[MAXM];

int N, M, K, Si, Ei;

ll solve() {
	{
		vector<pii> OV;
		for(int i = N; i--;) OV.eb(-B[i], -(i+1));
		for(int i = M; i--;) OV.eb(-E[i], i+1);
		sorv(OV);

		auto f = [&](int x) {
			set<int> PQ;
			for(auto &ev : OV) {
				int idx = ev.se;
				if(idx < 0) {
					idx = -idx-1;
					PQ.insert(idx);
				} else {
					idx--;
					if(D[idx] <= x) {
						auto it = PQ.find(D[idx]);
						PV.eb(A[*it], E[idx]);
						PV.eb(A[*prev(it)], E[idx]);
					} else if(x <= C[idx]) {
						auto it = PQ.find(C[idx]);
						PV.eb(A[*it], E[idx]);
						PV.eb(A[*next(it)], E[idx]);
					} else {
						auto it = PQ.upper_bound(x-1);
						if(PQ.begin() != it) {
							it--;
							if(C[idx] <= *it && *it <= D[idx])
								PV.eb(A[*it], E[idx]);
						}
						it = PQ.upper_bound(x);
						if(PQ.end() != it && C[idx] <= *it && *it <= D[idx])
							PV.eb(A[*it], E[idx]);
					}
				}
			}
		};
		f(Si); f(Ei);
	}

	{
		vector<EVT> EV;
		for(int i = M; i--;) {
			EV.eb(0, pii(A[C[i]], E[i]));
			EV.eb(2, pii(A[D[i]], E[i]));
		}
		for(auto &v : PV) EV.eb(1, v);
		sorv(EV);

		multiset<int> PQ;
		for(auto &ev : EV) {
			if(!ev.type) PQ.insert(ev.p.se);
			else if(1 == ev.type) {
				auto it = PQ.upper_bound(ev.p.se);
				if(PQ.end() != it) PV.eb(ev.p.fi, *it);
				if(PQ.begin() != it && *prev(it) == ev.p.se) it--;
				if(PQ.begin() != it) PV.eb(ev.p.fi, *prev(it));
			} else PQ.erase(PQ.find(ev.p.se));
		}
	}

	PV.eb(A[Si], 0); PV.eb(A[Ei], 0);
	for(int i = M; i--;) {
		if(C[i] <= Si && Si <= D[i] && E[i] <= B[Si]) PV.eb(A[Si], E[i]);
		if(C[i] <= Ei && Ei <= D[i] && E[i] <= B[Ei]) PV.eb(A[Ei], E[i]);
	}

	sorv(PV); univ(PV);
	{
		vector<pii> V; K = sz(PV);
		for(int i = 0, s = 0, e; i < N; i++, s = e) {
			for(e = s; e < K && PV[e].fi == A[i]; e++);
			for(int j = s; j < e; j++)
				if(PV[j].se <= B[i]) V.eb(PV[j]);
		}
		swap(PV, V);
	}
	K = sz(PV);
	fill(dp, dp+MAXK, INFLL);
	{ int x = A[Si]; for(Si = 0; PV[Si].fi != x || PV[Si].se; Si++); }
	{ int x = A[Ei]; for(Ei = 0; PV[Ei].fi != x || PV[Ei].se; Ei++); }

	for(int i = 1; i < K; i++)
		if(PV[i-1].fi == PV[i].fi) fg(G, i-1, i);

	{
		auto cmp = [&](const pii &a, const pii &b) {
			if(a.se != b.se) return a.se < b.se;
			return a.fi < b.fi;
		};
		vector<pair<pii, int>> _PV(K);
		for(int i = K; i--;) _PV[i] = {PV[i], i};
		sort(allv(_PV), [&](const pair<pii, int> &a, const pair<pii, int> &b) { return cmp(a.fi, b.fi); });

		vector<int> OV;
		for(int i = M; i--;) OV.eb(i);
		sort(allv(OV), [&](int a, int b) { return cmp({A[C[a]], E[a]}, {A[C[b]], E[b]}); });

		for(int i = 0, j = 0, idx; i < M; i++) {
			idx = OV[i];
			for(; j < K && cmp(_PV[j].fi, {A[C[idx]], E[idx]}); j++);
			for(j++; j < K && _PV[j].fi.se == E[idx] && _PV[j].fi.fi <= A[D[idx]]; j++) fg(G, _PV[j-1].se, _PV[j].se);
			if(j) j--;
		}
	}
	
	{
		priority_queue<pli, vector<pli>, greater<pli>> PQ;
		dp[Si] = 0; PQ.emplace(0, Si);
		for(ll dst; !PQ.empty();) {
			int idx; tie(dst, idx) = PQ.top(); PQ.pop();
			if(dp[idx] < dst) continue;
			for(int v : G[idx]) {
				ll ndst = dst + abs(PV[idx].fi - PV[v].fi) + abs(PV[idx].se - PV[v].se);
				if(dp[v] <= ndst) continue;
				dp[v] = ndst;
				PQ.emplace(ndst, v);
			}
		}
	}
	return dp[Ei] >= INFLL ? -1 : dp[Ei];
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	::N = sz(x); ::M = sz(l);
	for(int i = 0; i < ::N; i++) {
		::A[i] = x[i];
		::B[i] = h[i];
	}
	for(int i = 0; i < ::M; i++) {
		::C[i] = l[i];
		::D[i] = r[i];
		::E[i] = y[i];
	}
	::Si = s; ::Ei = g;
	return solve();
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	62968 KB	Output is correct
2	Correct	59 ms	62968 KB	Output is correct
3	Correct	60 ms	62944 KB	Output is correct
4	Correct	59 ms	62968 KB	Output is correct
5	Correct	60 ms	62968 KB	Output is correct
6	Correct	70 ms	62940 KB	Output is correct
7	Correct	60 ms	62972 KB	Output is correct
8	Correct	61 ms	62940 KB	Output is correct
9	Correct	64 ms	62968 KB	Output is correct
10	Correct	59 ms	62968 KB	Output is correct
11	Correct	59 ms	62968 KB	Output is correct
12	Correct	60 ms	62968 KB	Output is correct
13	Correct	59 ms	62968 KB	Output is correct
14	Correct	60 ms	62968 KB	Output is correct
15	Correct	60 ms	62968 KB	Output is correct
16	Correct	60 ms	62968 KB	Output is correct
17	Correct	60 ms	63044 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	62992 KB	Output is correct
2	Correct	60 ms	63068 KB	Output is correct
3	Correct	775 ms	90564 KB	Output is correct
4	Correct	1035 ms	100056 KB	Output is correct
5	Correct	630 ms	87516 KB	Output is correct
6	Correct	606 ms	85156 KB	Output is correct
7	Correct	616 ms	87516 KB	Output is correct
8	Correct	921 ms	93848 KB	Output is correct
9	Correct	944 ms	94516 KB	Output is correct
10	Correct	1119 ms	104124 KB	Output is correct
11	Correct	726 ms	85540 KB	Output is correct
12	Correct	684 ms	81464 KB	Output is correct
13	Correct	1187 ms	108244 KB	Output is correct
14	Correct	590 ms	79620 KB	Output is correct
15	Correct	628 ms	81344 KB	Output is correct
16	Correct	586 ms	81752 KB	Output is correct
17	Correct	574 ms	81140 KB	Output is correct
18	Correct	654 ms	86820 KB	Output is correct
19	Correct	78 ms	63948 KB	Output is correct
20	Correct	277 ms	72604 KB	Output is correct
21	Correct	549 ms	80640 KB	Output is correct
22	Correct	595 ms	81384 KB	Output is correct
23	Correct	651 ms	83704 KB	Output is correct
24	Correct	549 ms	80060 KB	Output is correct
25	Correct	560 ms	79824 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	68516 KB	Output is correct
2	Correct	1262 ms	123536 KB	Output is correct
3	Correct	1418 ms	128280 KB	Output is correct
4	Correct	1753 ms	130848 KB	Output is correct
5	Correct	1853 ms	130852 KB	Output is correct
6	Correct	1736 ms	125788 KB	Output is correct
7	Correct	906 ms	98292 KB	Output is correct
8	Correct	687 ms	79956 KB	Output is correct
9	Correct	1750 ms	120688 KB	Output is correct
10	Correct	687 ms	87648 KB	Output is correct
11	Correct	99 ms	64316 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	68516 KB	Output is correct
2	Correct	1262 ms	123536 KB	Output is correct
3	Correct	1418 ms	128280 KB	Output is correct
4	Correct	1753 ms	130848 KB	Output is correct
5	Correct	1853 ms	130852 KB	Output is correct
6	Correct	1736 ms	125788 KB	Output is correct
7	Correct	906 ms	98292 KB	Output is correct
8	Correct	687 ms	79956 KB	Output is correct
9	Correct	1750 ms	120688 KB	Output is correct
10	Correct	687 ms	87648 KB	Output is correct
11	Correct	99 ms	64316 KB	Output is correct
12	Correct	1414 ms	130144 KB	Output is correct
13	Correct	1283 ms	134904 KB	Output is correct
14	Correct	1921 ms	134888 KB	Output is correct
15	Correct	1252 ms	114396 KB	Output is correct
16	Correct	1356 ms	114568 KB	Output is correct
17	Correct	1644 ms	124668 KB	Output is correct
18	Correct	1252 ms	114516 KB	Output is correct
19	Correct	1332 ms	114716 KB	Output is correct
20	Correct	1002 ms	100704 KB	Output is correct
21	Correct	267 ms	67828 KB	Output is correct
22	Correct	941 ms	116624 KB	Output is correct
23	Correct	895 ms	110796 KB	Output is correct
24	Correct	695 ms	92452 KB	Output is correct
25	Correct	845 ms	106372 KB	Output is correct
26	Correct	590 ms	82564 KB	Output is correct
27	Correct	2073 ms	134856 KB	Output is correct
28	Correct	1273 ms	133448 KB	Output is correct
29	Correct	1847 ms	129716 KB	Output is correct
30	Correct	951 ms	101236 KB	Output is correct
31	Correct	1644 ms	124760 KB	Output is correct
32	Correct	629 ms	86604 KB	Output is correct
33	Correct	614 ms	86952 KB	Output is correct
34	Correct	643 ms	88268 KB	Output is correct
35	Correct	767 ms	94900 KB	Output is correct
36	Correct	666 ms	85976 KB	Output is correct
37	Correct	550 ms	82172 KB	Output is correct
38	Correct	576 ms	83160 KB	Output is correct
39	Correct	643 ms	85580 KB	Output is correct
40	Correct	545 ms	83124 KB	Output is correct
41	Correct	556 ms	82516 KB	Output is correct

Subtask #5

43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	62968 KB	Output is correct
2	Correct	59 ms	62968 KB	Output is correct
3	Correct	60 ms	62944 KB	Output is correct
4	Correct	59 ms	62968 KB	Output is correct
5	Correct	60 ms	62968 KB	Output is correct
6	Correct	70 ms	62940 KB	Output is correct
7	Correct	60 ms	62972 KB	Output is correct
8	Correct	61 ms	62940 KB	Output is correct
9	Correct	64 ms	62968 KB	Output is correct
10	Correct	59 ms	62968 KB	Output is correct
11	Correct	59 ms	62968 KB	Output is correct
12	Correct	60 ms	62968 KB	Output is correct
13	Correct	59 ms	62968 KB	Output is correct
14	Correct	60 ms	62968 KB	Output is correct
15	Correct	60 ms	62968 KB	Output is correct
16	Correct	60 ms	62968 KB	Output is correct
17	Correct	60 ms	63044 KB	Output is correct
18	Correct	70 ms	62992 KB	Output is correct
19	Correct	60 ms	63068 KB	Output is correct
20	Correct	775 ms	90564 KB	Output is correct
21	Correct	1035 ms	100056 KB	Output is correct
22	Correct	630 ms	87516 KB	Output is correct
23	Correct	606 ms	85156 KB	Output is correct
24	Correct	616 ms	87516 KB	Output is correct
25	Correct	921 ms	93848 KB	Output is correct
26	Correct	944 ms	94516 KB	Output is correct
27	Correct	1119 ms	104124 KB	Output is correct
28	Correct	726 ms	85540 KB	Output is correct
29	Correct	684 ms	81464 KB	Output is correct
30	Correct	1187 ms	108244 KB	Output is correct
31	Correct	590 ms	79620 KB	Output is correct
32	Correct	628 ms	81344 KB	Output is correct
33	Correct	586 ms	81752 KB	Output is correct
34	Correct	574 ms	81140 KB	Output is correct
35	Correct	654 ms	86820 KB	Output is correct
36	Correct	78 ms	63948 KB	Output is correct
37	Correct	277 ms	72604 KB	Output is correct
38	Correct	549 ms	80640 KB	Output is correct
39	Correct	595 ms	81384 KB	Output is correct
40	Correct	651 ms	83704 KB	Output is correct
41	Correct	549 ms	80060 KB	Output is correct
42	Correct	560 ms	79824 KB	Output is correct
43	Correct	248 ms	68516 KB	Output is correct
44	Correct	1262 ms	123536 KB	Output is correct
45	Correct	1418 ms	128280 KB	Output is correct
46	Correct	1753 ms	130848 KB	Output is correct
47	Correct	1853 ms	130852 KB	Output is correct
48	Correct	1736 ms	125788 KB	Output is correct
49	Correct	906 ms	98292 KB	Output is correct
50	Correct	687 ms	79956 KB	Output is correct
51	Correct	1750 ms	120688 KB	Output is correct
52	Correct	687 ms	87648 KB	Output is correct
53	Correct	99 ms	64316 KB	Output is correct
54	Correct	1414 ms	130144 KB	Output is correct
55	Correct	1283 ms	134904 KB	Output is correct
56	Correct	1921 ms	134888 KB	Output is correct
57	Correct	1252 ms	114396 KB	Output is correct
58	Correct	1356 ms	114568 KB	Output is correct
59	Correct	1644 ms	124668 KB	Output is correct
60	Correct	1252 ms	114516 KB	Output is correct
61	Correct	1332 ms	114716 KB	Output is correct
62	Correct	1002 ms	100704 KB	Output is correct
63	Correct	267 ms	67828 KB	Output is correct
64	Correct	941 ms	116624 KB	Output is correct
65	Correct	895 ms	110796 KB	Output is correct
66	Correct	695 ms	92452 KB	Output is correct
67	Correct	845 ms	106372 KB	Output is correct
68	Correct	590 ms	82564 KB	Output is correct
69	Correct	2073 ms	134856 KB	Output is correct
70	Correct	1273 ms	133448 KB	Output is correct
71	Correct	1847 ms	129716 KB	Output is correct
72	Correct	951 ms	101236 KB	Output is correct
73	Correct	1644 ms	124760 KB	Output is correct
74	Correct	629 ms	86604 KB	Output is correct
75	Correct	614 ms	86952 KB	Output is correct
76	Correct	643 ms	88268 KB	Output is correct
77	Correct	767 ms	94900 KB	Output is correct
78	Correct	666 ms	85976 KB	Output is correct
79	Correct	550 ms	82172 KB	Output is correct
80	Correct	576 ms	83160 KB	Output is correct
81	Correct	643 ms	85580 KB	Output is correct
82	Correct	545 ms	83124 KB	Output is correct
83	Correct	556 ms	82516 KB	Output is correct
84	Correct	222 ms	68264 KB	Output is correct
85	Correct	1177 ms	114768 KB	Output is correct
86	Correct	1651 ms	123068 KB	Output is correct
87	Correct	212 ms	70732 KB	Output is correct
88	Correct	332 ms	70584 KB	Output is correct
89	Correct	213 ms	70584 KB	Output is correct
90	Correct	124 ms	65548 KB	Output is correct
91	Correct	71 ms	63228 KB	Output is correct
92	Correct	96 ms	64936 KB	Output is correct
93	Correct	533 ms	81472 KB	Output is correct
94	Correct	207 ms	67792 KB	Output is correct
95	Correct	776 ms	98348 KB	Output is correct
96	Correct	710 ms	94608 KB	Output is correct
97	Correct	623 ms	85672 KB	Output is correct
98	Correct	663 ms	92488 KB	Output is correct
99	Correct	1184 ms	106948 KB	Output is correct
100	Correct	1471 ms	120568 KB	Output is correct
101	Correct	1340 ms	106364 KB	Output is correct
102	Correct	770 ms	89504 KB	Output is correct
103	Correct	597 ms	83984 KB	Output is correct
104	Correct	601 ms	84432 KB	Output is correct
105	Correct	625 ms	85700 KB	Output is correct
106	Correct	609 ms	84516 KB	Output is correct
107	Correct	622 ms	84476 KB	Output is correct
108	Correct	173 ms	68220 KB	Output is correct
109	Correct	1495 ms	117600 KB	Output is correct
110	Correct	920 ms	104656 KB	Output is correct
111	Correct	877 ms	106620 KB	Output is correct
112	Correct	711 ms	92196 KB	Output is correct
113	Correct	704 ms	88420 KB	Output is correct