Submission #145196

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145196	2019-08-19T08:42:34 Z	ecnerwala	Sky Walking (IOI19_walk)	C++14	100 / 100	1547 ms	133740 KB

walk

#include "walk.h"

#include<bits/stdc++.h>

namespace {

namespace min_distance_set {

using namespace std;
using ll = long long;
using height_t = pair<ll, int>;

const ll INF = 1e18;

struct height_container {
	set<height_t> alive;
	map<height_t, ll> value;

	ll query(height_t h) {
		ll ans = INF;
		auto it = value.lower_bound(h);
		if (it != value.end()) {
			ans = min(ans, it->second + abs(h.first - it->first.first));
		}
		if (it != value.begin()) {
			--it;
			ans = min(ans, it->second + abs(h.first - it->first.first));
		}
		return ans;
	}

	void insert_line(height_t h, ll v = INF) {
		assert(!alive.count(h));
		alive.insert(h);
		if (v == INF || v >= query(h)) {
			return;
		}
		assert(!value.count(h));
		auto emp = value.emplace(h, v);
		assert(emp.second);
		while (true) {
			auto it = emp.first;
			++it;
			if (it == value.end()) break;
			if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) {
				value.erase(it);
			} else {
				break;
			}
		}
		while (true) {
			auto it = emp.first;
			if (it == value.begin()) break;
			--it;
			if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) {
				value.erase(it);
			} else {
				break;
			}
		}
	}

	void delete_line(height_t h) {
		assert(alive.count(h));

		if (value.count(h)) {
			auto pt = alive.find(h);
			auto nt = pt;
			if (pt != alive.begin()) {
				--pt;
				ll v = query(*pt);
				value.emplace(*pt, v);
			}

			if (nt != alive.end()) {
				++nt;
				if (nt != alive.end()) {
					ll v = query(*nt);
					value.emplace(*nt, v);
				}
			}
			value.erase(h);
		}

		alive.erase(h);
	}

	void insert_all(vector<height_t> v) {
		for (height_t h : v) insert_line(h);
	}
	void delete_all(vector<height_t> v) {
		for (height_t h : v) delete_line(h);
	}

	friend std::ostream& operator << (std::ostream& o, const height_container& h) {
		o << "[";
		for (const auto& it : h.alive) {
			o << "(" << it.first << "," << it.second << ")";
			o << ": ";
			if (h.value.count(it)) {
				o << h.value.at(it);
			} else {
				o << "_";
			}
			o << ", ";
		}
		o << "]";
		return o;
	}
};

ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) {
	int N = int(X_.size());
	int M = int(Y_.size());

	vector<ll> X(X_.begin(), X_.end());
	vector<height_t> H(N);
	for (int i = 0; i < N; i++) {
		H[i] = {H_[i], i};
	}

	vector<height_t> Y(M);
	for (int e = 0; e < M; e++) {
		Y[e] = {Y_[e], -1-e};
	}

	if (S > T) swap(S, T);
	assert(S < T);

	// peak index
	int P = int(max_element(H.begin() + S, H.begin() + T + 1) - H.begin());
	assert(H[P] >= H[S] && H[P] >= H[T]);

	const height_t BOTTOM = {0, -M-1};
	const height_t TOP = {INF, N};

	vector<vector<height_t>> lefts(N);
	vector<vector<height_t>> rights(N);
	for (int e = 0; e < M; e++) {
		lefts[L[e]].push_back(Y[e]);
		rights[R[e]].push_back(Y[e]);
	}

	priority_queue<height_t, vector<height_t>, greater<height_t>> highEdges;
	for (int e = 0; e < M; e++) {
		highEdges.push(Y[e]);
	}

	if (false) { // left->right only
		if (S == 0 && T == N-1) {
			height_container hc;
			hc.insert_line(BOTTOM, 0);
			rights[S].push_back(BOTTOM);
			lefts[T].push_back(BOTTOM);
			for (int i = 0; i < N; i++) {
				hc.insert_all(lefts[i]);
				hc.delete_all(rights[i]);
			}


			ll ans = hc.query(BOTTOM);
			if (ans == INF) {
				return -1;
			}
			return ans + (X[T] - X[S]);
		} else {
			return -2;
		}
	}

	height_container sLeft, sRight, tLeft, tRight;
	sLeft.insert_line({0, -M-1}, 0);
	sRight.insert_line({0, -M-1}, 0);
	tLeft.insert_line({0, -M-1}, 0);
	tRight.insert_line({0, -M-1}, 0);

	lefts[S].push_back({0, -M-1});
	rights[S].push_back({0, -M-1});
	lefts[T].push_back({0, -M-1});
	rights[T].push_back({0, -M-1});

	int sl = S, sr = S, tl = T, tr = T;

	ll ans = INF;

	bool crossedMid = false;

	while (true) {
		height_t evtHeight = TOP;
		if (!highEdges.empty()) {
			evtHeight = min(evtHeight, highEdges.top());
		}
		if (sl > 0) {
			evtHeight = min(evtHeight, H[sl]);
		}

		if (!crossedMid) {
			evtHeight = min(evtHeight, H[sr]);
			evtHeight = min(evtHeight, H[tl]);
		}

		if (tr < N-1) {
			evtHeight = min(evtHeight, H[tr]);
		}

		if (evtHeight == TOP) break;

		if (!highEdges.empty() && evtHeight == highEdges.top()) {
			// do the thing
			int e = -1-highEdges.top().second;
			highEdges.pop();

			if (crossedMid) {
				assert(Y[e] > H[P]);
				assert(L[e] < S || L[e] > T);
				assert(R[e] < S || R[e] > T);
				if (L[e] < P && P < R[e]) {
					// just connect the two, it crosses
					ans = min(ans, sLeft.query(Y[e]) + tRight.query(Y[e]) + 2 * (X[S] - X[sl]) + 2 * (X[tr] - X[T]));

					// it's never optimal to go further, so we could just break
					//break;

					sLeft.insert_line(Y[e]);
					tRight.insert_line(Y[e]);
				}
			} else {
				assert(Y[e] <= H[P]);
				if (L[e] <= S && S <= R[e]) {
					ll rval = sRight.query(Y[e]) + 2 * (X[sr] - X[S]);
					ll lval = sLeft.query(Y[e]) + 2 * (X[S] - X[sl]);

					sLeft.insert_line(Y[e], rval);
					sRight.insert_line(Y[e], lval);
				}
				if (L[e] <= T && T <= R[e]) {
					ll rval = tRight.query(Y[e]) + 2 * (X[tr] - X[T]);
					ll lval = tLeft.query(Y[e]) + 2 * (X[T] - X[tl]);

					tLeft.insert_line(Y[e], rval);
					tRight.insert_line(Y[e], lval);
				}
			}
		} else if (!crossedMid && evtHeight == H[P]) {
			assert(sr == P && tl == P);

			for (auto it : sRight.value) {
				ans = min(ans, it.second + tLeft.query(it.first));
			}

			crossedMid = true;
		} else if (sl > 0 && evtHeight == H[sl]) {
			sLeft.delete_all(lefts[sl]);
			--sl;
			sLeft.insert_all(rights[sl]);
		} else if (sr < P && evtHeight == H[sr]) {
			sRight.delete_all(rights[sr]);
			++sr;
			sRight.insert_all(lefts[sr]);
		} else if (tl > P && evtHeight == H[tl]) {
			tLeft.delete_all(lefts[tl]);
			--tl;
			tLeft.insert_all(rights[tl]);
		} else if (tr < N-1 && evtHeight == H[tr]) {
			tRight.delete_all(rights[tr]);
			++tr;
			tRight.insert_all(lefts[tr]);
		} else assert(false);
	}

	//cerr << ans << '\n';

	if (ans == INF) return -1;
	else return ans + (X[T] - X[S]);
}

} // namespace min_distance_set

namespace min_distance_dijk {

using namespace std;
using ll = long long;
using height_t = pair<int, int>;

ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) {
	int N = int(X_.size());
	int M = int(Y_.size());

	vector<ll> X(X_.begin(), X_.end());
	vector<height_t> H(N);
	for (int i = 0; i < N; i++) {
		H[i] = {H_[i], i};
	}

	vector<height_t> Y(M);
	for (int e = 0; e < M; e++) {
		Y[e] = {Y_[e], -1-e};
	}

	vector<vector<height_t>> needs(N);

	vector<height_t> heights;
	heights.insert(heights.end(), H.begin(), H.end());
	heights.insert(heights.end(), Y.begin(), Y.end());
	sort(heights.begin(), heights.end());
	reverse(heights.begin(), heights.end());

	set<int> posts;
	for (height_t h : heights) {
		if (h.second >= 0) {
			// it's a post
			posts.insert(h.second);
		} else {
			int e = -1-h.second;
			set<int> eNeeds;
			eNeeds.insert(L[e]);
			eNeeds.insert(R[e]);
			for (int p : {S, T}) {
				if (L[e] <= p && p <= R[e]) {
					{
						auto it = posts.lower_bound(p);
						if (it != posts.end()) {
							eNeeds.insert(*it);
						}
					}
					{
						auto it = posts.upper_bound(p);
						if (it != posts.begin()) {
							eNeeds.insert(*--it);
						}
					}
				}
			}
			for (int i : eNeeds) {
				needs[i].push_back(h);
			}
		}
	}

	int V = 0;
	vector<vector<pair<int, ll>>> adj;

	map<height_t, pair<int, int>> prvVert;
	set<height_t> inters;
	vector<vector<height_t>> lefts(N);
	vector<vector<height_t>> rights(N);
	for (int e = 0; e < M; e++) {
		lefts[L[e]].push_back(Y[e]);
		rights[R[e]].push_back(Y[e]);
	}

	const height_t SBOTTOM(0, -1-M);
	lefts[S].push_back(SBOTTOM);
	rights[S].push_back(SBOTTOM);
	needs[S].push_back(SBOTTOM);

	const height_t TBOTTOM(0, -1-(M+1));
	lefts[T].push_back(TBOTTOM);
	rights[T].push_back(TBOTTOM);
	needs[T].push_back(TBOTTOM);


	int Svert = -1, Tvert = -1;
	for (int i = 0; i < N; i++) {
		for (height_t h : lefts[i]) {
			inters.insert(h);
		}

		reverse(needs[i].begin(), needs[i].end()); // should now be sorted

		vector<height_t> realNeeds;
		for (height_t h : needs[i]) {
			auto it = inters.find(h);
			assert(it != inters.end());

			auto kt = it;
			if (kt != inters.begin()) {
				--kt;
				if (realNeeds.empty() || realNeeds.back() < *kt) {
					realNeeds.push_back(*kt);
				}
			}

			if (realNeeds.empty() || realNeeds.back() < *it) {
				realNeeds.push_back(*it);
			}

			auto jt = it; ++jt;
			if (jt != inters.end()) {
				if (realNeeds.empty() || realNeeds.back() < *jt) {
					realNeeds.push_back(*jt);
				}
			}
		}

		while (!realNeeds.empty() && realNeeds.back() > H[i]) realNeeds.pop_back();

		assert(V == int(adj.size()));
		adj.resize(V + int(realNeeds.size()));

		for (int z = 0; z < int(realNeeds.size()); z++) {
			height_t h = realNeeds[z];
			int v = V + z;

			auto it = prvVert.find(h);
			if (it != prvVert.end()) {
				int u = it->second.second;
				ll d = X[i] - X[it->second.first];
				adj[v].emplace_back(u, d);
				adj[u].emplace_back(v, d);

				it->second = {i, v};
			} else {
				prvVert.emplace(h, pair<int, int>{i, v});
			}
		}

		for (int z = 0; z+1 < int(realNeeds.size()); z++) {
			assert(realNeeds[z] < realNeeds[z+1]);
			int v = V + z + 1;
			int u = V + z;
			ll d = realNeeds[z+1].first - realNeeds[z].first;
			adj[v].emplace_back(u, d);
			adj[u].emplace_back(v, d);
		}

		if (i == S) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == SBOTTOM);
			Svert = V + 0;
		}
		if (i == T) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == TBOTTOM);
			Tvert = V + 0;
		}

		V += int(realNeeds.size());

		for (height_t h : rights[i]) {
			inters.erase(h);
		}
	}

	const ll INF = 1e18;
	vector<ll> dist(V, INF);
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dist[Svert] = 0;
	pq.emplace(0, Svert);
	while (!pq.empty()) {
		int cur = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if (dist[cur] != d) continue;

		if (cur == Tvert) return d;

		for (auto it : adj[cur]) {
			int nxt = it.first;
			ll nd = d + it.second;
			if (nd < dist[nxt]) {
				dist[nxt] = nd;
				pq.emplace(nd, nxt);
			}
		}
	}

	return -1;
}

} // namespace min_distance_dijk

} // anonymous namespace

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 T) {
	if (false) {
		return min_distance_set::min_distance(X, H, L, R, Y, S, T);
	} else {
		return min_distance_dijk::min_distance(X, H, L, R, Y, S, T);
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	523 ms	65292 KB	Output is correct
4	Correct	799 ms	83140 KB	Output is correct
5	Correct	493 ms	67244 KB	Output is correct
6	Correct	485 ms	63596 KB	Output is correct
7	Correct	497 ms	67560 KB	Output is correct
8	Correct	604 ms	76176 KB	Output is correct
9	Correct	679 ms	77540 KB	Output is correct
10	Correct	813 ms	85156 KB	Output is correct
11	Correct	525 ms	61236 KB	Output is correct
12	Correct	500 ms	54592 KB	Output is correct
13	Correct	823 ms	88804 KB	Output is correct
14	Correct	445 ms	51088 KB	Output is correct
15	Correct	488 ms	53596 KB	Output is correct
16	Correct	421 ms	54764 KB	Output is correct
17	Correct	454 ms	53312 KB	Output is correct
18	Correct	422 ms	61988 KB	Output is correct
19	Correct	16 ms	2936 KB	Output is correct
20	Correct	178 ms	26216 KB	Output is correct
21	Correct	427 ms	50728 KB	Output is correct
22	Correct	441 ms	54836 KB	Output is correct
23	Correct	503 ms	65940 KB	Output is correct
24	Correct	429 ms	54288 KB	Output is correct
25	Correct	466 ms	53528 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	22216 KB	Output is correct
2	Correct	906 ms	80912 KB	Output is correct
3	Correct	1006 ms	86124 KB	Output is correct
4	Correct	1214 ms	107028 KB	Output is correct
5	Correct	1547 ms	109652 KB	Output is correct
6	Correct	1301 ms	102200 KB	Output is correct
7	Correct	557 ms	63376 KB	Output is correct
8	Correct	425 ms	55384 KB	Output is correct
9	Correct	1419 ms	100608 KB	Output is correct
10	Correct	517 ms	67024 KB	Output is correct
11	Correct	41 ms	9328 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	22216 KB	Output is correct
2	Correct	906 ms	80912 KB	Output is correct
3	Correct	1006 ms	86124 KB	Output is correct
4	Correct	1214 ms	107028 KB	Output is correct
5	Correct	1547 ms	109652 KB	Output is correct
6	Correct	1301 ms	102200 KB	Output is correct
7	Correct	557 ms	63376 KB	Output is correct
8	Correct	425 ms	55384 KB	Output is correct
9	Correct	1419 ms	100608 KB	Output is correct
10	Correct	517 ms	67024 KB	Output is correct
11	Correct	41 ms	9328 KB	Output is correct
12	Correct	992 ms	87256 KB	Output is correct
13	Correct	1130 ms	104000 KB	Output is correct
14	Correct	1463 ms	110236 KB	Output is correct
15	Correct	944 ms	86384 KB	Output is correct
16	Correct	972 ms	90116 KB	Output is correct
17	Correct	1161 ms	108212 KB	Output is correct
18	Correct	921 ms	86196 KB	Output is correct
19	Correct	1038 ms	89748 KB	Output is correct
20	Correct	632 ms	62904 KB	Output is correct
21	Correct	115 ms	19560 KB	Output is correct
22	Correct	687 ms	83748 KB	Output is correct
23	Correct	580 ms	79296 KB	Output is correct
24	Correct	471 ms	61088 KB	Output is correct
25	Correct	565 ms	74652 KB	Output is correct
26	Correct	414 ms	51944 KB	Output is correct
27	Correct	1470 ms	109568 KB	Output is correct
28	Correct	944 ms	102896 KB	Output is correct
29	Correct	1305 ms	102852 KB	Output is correct
30	Correct	588 ms	65740 KB	Output is correct
31	Correct	1264 ms	100944 KB	Output is correct
32	Correct	484 ms	59560 KB	Output is correct
33	Correct	466 ms	61636 KB	Output is correct
34	Correct	452 ms	66212 KB	Output is correct
35	Correct	553 ms	67320 KB	Output is correct
36	Correct	507 ms	59680 KB	Output is correct
37	Correct	440 ms	51912 KB	Output is correct
38	Correct	415 ms	56028 KB	Output is correct
39	Correct	503 ms	67292 KB	Output is correct
40	Correct	461 ms	55516 KB	Output is correct
41	Correct	439 ms	54544 KB	Output is correct

Subtask #5

43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	523 ms	65292 KB	Output is correct
21	Correct	799 ms	83140 KB	Output is correct
22	Correct	493 ms	67244 KB	Output is correct
23	Correct	485 ms	63596 KB	Output is correct
24	Correct	497 ms	67560 KB	Output is correct
25	Correct	604 ms	76176 KB	Output is correct
26	Correct	679 ms	77540 KB	Output is correct
27	Correct	813 ms	85156 KB	Output is correct
28	Correct	525 ms	61236 KB	Output is correct
29	Correct	500 ms	54592 KB	Output is correct
30	Correct	823 ms	88804 KB	Output is correct
31	Correct	445 ms	51088 KB	Output is correct
32	Correct	488 ms	53596 KB	Output is correct
33	Correct	421 ms	54764 KB	Output is correct
34	Correct	454 ms	53312 KB	Output is correct
35	Correct	422 ms	61988 KB	Output is correct
36	Correct	16 ms	2936 KB	Output is correct
37	Correct	178 ms	26216 KB	Output is correct
38	Correct	427 ms	50728 KB	Output is correct
39	Correct	441 ms	54836 KB	Output is correct
40	Correct	503 ms	65940 KB	Output is correct
41	Correct	429 ms	54288 KB	Output is correct
42	Correct	466 ms	53528 KB	Output is correct
43	Correct	174 ms	22216 KB	Output is correct
44	Correct	906 ms	80912 KB	Output is correct
45	Correct	1006 ms	86124 KB	Output is correct
46	Correct	1214 ms	107028 KB	Output is correct
47	Correct	1547 ms	109652 KB	Output is correct
48	Correct	1301 ms	102200 KB	Output is correct
49	Correct	557 ms	63376 KB	Output is correct
50	Correct	425 ms	55384 KB	Output is correct
51	Correct	1419 ms	100608 KB	Output is correct
52	Correct	517 ms	67024 KB	Output is correct
53	Correct	41 ms	9328 KB	Output is correct
54	Correct	992 ms	87256 KB	Output is correct
55	Correct	1130 ms	104000 KB	Output is correct
56	Correct	1463 ms	110236 KB	Output is correct
57	Correct	944 ms	86384 KB	Output is correct
58	Correct	972 ms	90116 KB	Output is correct
59	Correct	1161 ms	108212 KB	Output is correct
60	Correct	921 ms	86196 KB	Output is correct
61	Correct	1038 ms	89748 KB	Output is correct
62	Correct	632 ms	62904 KB	Output is correct
63	Correct	115 ms	19560 KB	Output is correct
64	Correct	687 ms	83748 KB	Output is correct
65	Correct	580 ms	79296 KB	Output is correct
66	Correct	471 ms	61088 KB	Output is correct
67	Correct	565 ms	74652 KB	Output is correct
68	Correct	414 ms	51944 KB	Output is correct
69	Correct	1470 ms	109568 KB	Output is correct
70	Correct	944 ms	102896 KB	Output is correct
71	Correct	1305 ms	102852 KB	Output is correct
72	Correct	588 ms	65740 KB	Output is correct
73	Correct	1264 ms	100944 KB	Output is correct
74	Correct	484 ms	59560 KB	Output is correct
75	Correct	466 ms	61636 KB	Output is correct
76	Correct	452 ms	66212 KB	Output is correct
77	Correct	553 ms	67320 KB	Output is correct
78	Correct	507 ms	59680 KB	Output is correct
79	Correct	440 ms	51912 KB	Output is correct
80	Correct	415 ms	56028 KB	Output is correct
81	Correct	503 ms	67292 KB	Output is correct
82	Correct	461 ms	55516 KB	Output is correct
83	Correct	439 ms	54544 KB	Output is correct
84	Correct	140 ms	18296 KB	Output is correct
85	Correct	906 ms	91100 KB	Output is correct
86	Correct	1439 ms	120492 KB	Output is correct
87	Correct	115 ms	24796 KB	Output is correct
88	Correct	153 ms	25192 KB	Output is correct
89	Correct	116 ms	24808 KB	Output is correct
90	Correct	47 ms	7824 KB	Output is correct
91	Correct	3 ms	632 KB	Output is correct
92	Correct	32 ms	5248 KB	Output is correct
93	Correct	405 ms	49208 KB	Output is correct
94	Correct	119 ms	19688 KB	Output is correct
95	Correct	682 ms	87844 KB	Output is correct
96	Correct	587 ms	80240 KB	Output is correct
97	Correct	470 ms	61412 KB	Output is correct
98	Correct	545 ms	75056 KB	Output is correct
99	Correct	1514 ms	133740 KB	Output is correct
100	Correct	1153 ms	110156 KB	Output is correct
101	Correct	1245 ms	110340 KB	Output is correct
102	Correct	517 ms	64316 KB	Output is correct
103	Correct	497 ms	59828 KB	Output is correct
104	Correct	438 ms	62156 KB	Output is correct
105	Correct	473 ms	66912 KB	Output is correct
106	Correct	458 ms	61428 KB	Output is correct
107	Correct	485 ms	59888 KB	Output is correct
108	Correct	67 ms	8680 KB	Output is correct
109	Correct	1055 ms	86144 KB	Output is correct
110	Correct	931 ms	103460 KB	Output is correct
111	Correct	873 ms	102372 KB	Output is correct
112	Correct	540 ms	67168 KB	Output is correct
113	Correct	597 ms	63588 KB	Output is correct