oj.uz

Submission #807773

# Submission time Handle Problem Language Result Execution time Memory
807773 2023-08-05T01:08:56 Z math_rabbit_1028 Sky Walking (IOI19_walk) C++14
100 / 100
 2289 ms 199188 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, s, g;
vector<int> x, h, l, r, y;

struct sky {
	int lt, rt, val, idx;
} walk[101010];
bool compare(sky a, sky b) {
	if (a.rt == b.rt) return a.lt > b.lt;
	return a.rt < b.rt;
}
void sort_end() {
	for (int i = 0; i < m; i++) walk[i] = {l[i], r[i], y[i]};
	sort(walk, walk + m, compare);
	for (int i = 0; i < m; i++) {
		l[i] = walk[i].lt;
		r[i] = walk[i].rt;
		y[i] = walk[i].val;
	}
}

set<int> xpset, xmset;
vector< pair< pair<int, int>, int > > points;
vector<int> ylist;
vector<int> add[101010], rem[101010];
bool compval(sky a, sky b) {
	return a.val < b.val;
}
void get_points() {
	for (int i = 0; i < m; i++) ylist.push_back(walk[i].val);
	sort(ylist.begin(), ylist.end());
	ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
	
	for (int i = 0; i < m; i++) walk[i].idx = i;
	sort(walk, walk + m, compval);
	for (int i = 0; i < m; i++) 
		walk[i].val = lower_bound(ylist.begin(), ylist.end(), walk[i].val) - ylist.begin();

	for (int i = 0; i < n; i++) {
		int idx = upper_bound(ylist.begin(), ylist.end(), h[i]) - ylist.begin();
		rem[idx].push_back(i);
	}
	for (int i = 0; i < n; i++) xpset.insert(i);
	for (int i = 0; i < n; i++) xmset.insert(-i);

	int p = 0;
	for (int i = 0; i < m; i++) {
		while (p <= walk[i].val) {
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				xpset.erase(tar);
				xmset.erase(-tar);
			}
			p++;
		}

		if (walk[i].lt < s && s < walk[i].rt) {
			points.push_back({{*xpset.lower_bound(s), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.lower_bound(-s), ylist[walk[i].val]}, walk[i].idx});
		}
		if (walk[i].lt < g && g < walk[i].rt) {
			points.push_back({{*xpset.lower_bound(g), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.lower_bound(-g), ylist[walk[i].val]}, walk[i].idx});
		}
		points.push_back({{walk[i].lt, ylist[walk[i].val]}, walk[i].idx});
		points.push_back({{walk[i].rt, ylist[walk[i].val]}, walk[i].idx});
	}
	for (int i = 0; i < m; i++) rem[i].clear();

	sort(points.begin(), points.end());
	points.erase(unique(points.begin(), points.end()), points.end());
}

void print_points() {
	for (int i = 0; i < points.size(); i++) 
		cout << points[i].first.first << " " << points[i].first.second << "\n";
	cout << "\n";
}

set< pair<int, int> > pset, mset;
vector< pair< pair<int, int>, int > > vertex;
void get_updn() {
	for (int i = 0; i < m; i++) add[l[i]].push_back(i);
	for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);

	int p = 0;
	for (int i = 0; i < points.size(); i++) {
		int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
		while (p <= X) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				pset.insert({y[tar], -tar});
				mset.insert({-y[tar], -tar});
			}
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				pset.erase({y[tar], -tar});
				mset.erase({-y[tar], -tar});
			}
			p++;
		}

		if (pset.upper_bound({Y, -num}) == pset.end());
		else if (pset.upper_bound({Y, -num})->first <= h[X]) vertex.push_back({
			{X, pset.upper_bound({Y, -num})->first}, 
			-pset.upper_bound({Y, -num})->second
		});
		if (mset.upper_bound({-Y, -num}) == mset.end());
		else vertex.push_back({
			{X, -mset.upper_bound({-Y, -num})->first}, 
			-mset.upper_bound({-Y, -num})->second
		});
		vertex.push_back({{X, Y}, num});
	}
	for (int i = 0; i < n; i++) add[i].clear();
	for (int i = 0; i < n; i++) rem[i].clear();
	while (pset.size() > 0) pset.erase(pset.begin());
	while (mset.size() > 0) mset.erase(mset.begin());

	vertex.push_back({{s, 0}, -1});
	vertex.push_back({{g, 0}, -1});
	sort(vertex.begin(), vertex.end());
	vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}

void print_vertex() {
	for (int i = 0; i < vertex.size(); i++) 
		cout << vertex[i].first.first << " " << vertex[i].first.second << "\n";
	cout << "\n";
}

vector< pair<int, ll> > adj[2020202];
void link_updn() {
	for (int i = 0; i < m; i++) add[l[i]].push_back(i);
	for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);

	int p = 0;
	for (int i = 0; i < points.size(); i++) {
		int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
		while (p <= X) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				pset.insert({y[tar], -tar});
				mset.insert({-y[tar], -tar});
			}
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				pset.erase({y[tar], -tar});
				mset.erase({-y[tar], -tar});
			}
			p++;
		}

		int now = lower_bound(vertex.begin(), vertex.end(), points[i]) - vertex.begin();
		pair< pair<int, int>, int > up, dn;
		if (pset.upper_bound({Y, -num}) == pset.end());
		else if (pset.upper_bound({Y, -num})->first <= h[X]) {
			up = {
				{X, pset.upper_bound({Y, -num})->first}, 
				-pset.upper_bound({Y, -num})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin(),
				up.first.second - Y
			});
			adj[lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin()].push_back({
				now,
				up.first.second - Y
			});
		}
		if (mset.upper_bound({-Y, -num}) == mset.end());
		else {
			dn = {
				{X, -mset.upper_bound({-Y, -num})->first}, 
				-mset.upper_bound({-Y, -num})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin(),
				points[i].first.second - dn.first.second
			});
			adj[lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin()].push_back({
				now,
				points[i].first.second - dn.first.second
			});
		}
	}
	for (int i = 0; i < n; i++) add[i].clear();
	for (int i = 0; i < n; i++) rem[i].clear();
	while (pset.size() > 0) pset.erase(pset.begin());
	while (mset.size() > 0) mset.erase(mset.begin());
}

vector<int> xlist[101010];
void link_walk() {
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].second >= 0) xlist[vertex[i].second].push_back(vertex[i].first.first);
	}
	for (int i = 0; i < m; i++) sort(xlist[i].begin(), xlist[i].end());
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < xlist[i].size(); j++) {
			int lt = lower_bound(vertex.begin(), vertex.end(), make_pair(
				make_pair(xlist[i][j - 1], y[i]), i
			)) - vertex.begin();
			int rt = lower_bound(vertex.begin(), vertex.end(), make_pair(
				make_pair(xlist[i][j], y[i]), i
			)) - vertex.begin();
			adj[lt].push_back({rt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
			adj[rt].push_back({lt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
		}
	}
}

void link_sted() {
	int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].first.first == s) {
			adj[i].push_back({st, vertex[i].first.second});
			adj[st].push_back({i, vertex[i].first.second});
		}
	}
	
	int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].first.first == g) {
			adj[i].push_back({ed, vertex[i].first.second});
			adj[ed].push_back({i, vertex[i].first.second});
		}
	}
}

void print_adj() {
	for (int i = 0; i < vertex.size(); i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			cout << vertex[i].first.first << " " << vertex[i].first.second
				 << " " << vertex[adj[i][j].first].first.first 
				 << " " << vertex[adj[i][j].first].first.second
				 << " " << adj[i][j].second << "\n";
		}
	}
}	

ll dis[2020202];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
	for (int i = 0; i <= 2000000; i++) dis[i] = 1e18;
	int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
	dis[st] = 0;
	pq.push({-dis[st], st});
	while (!pq.empty()) {
		int now = pq.top().second; ll nowdis = -pq.top().first;
		pq.pop();
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i].first;
			if (dis[next] > nowdis + adj[now][i].second) {
				dis[next] = nowdis + adj[now][i].second;
				pq.push({-dis[next], next});
			}
		}
	}
}

void print_dis() {
	for (int i = 0; i < vertex.size(); i++) {
		cout << vertex[i].first.first << " " << vertex[i].first.second << " " << dis[i] << "\n";
	}
}

ll 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) {
	x = X; h = H; l = L; r = R; y = Y; s = S; g = G;
	n = x.size();
	m = l.size();
	sort_end();

	get_points();
	//print_points();

	get_updn();
	//print_vertex();

	link_updn();
	link_walk();
	link_sted();
	//print_adj();

	dijkstra();
	//print_dis();

	int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
	ll ans = dis[ed];
	if (ans >= 1e18) return -1;
	return ans;
}

Compilation message

walk.cpp: In function 'void get_points()':
walk.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_points()':
walk.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < points.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void get_updn()':
walk.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_vertex()':
walk.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for (int i = 0; i < vertex.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:199:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:204:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |   for (int j = 1; j < xlist[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:219:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:227:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_adj()':
walk.cpp:236:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:237:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |   for (int j = 0; j < adj[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:256:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |   for (int i = 0; i < adj[now].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void print_dis()':
walk.cpp:267:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 70444 KB Output is correct
2 Correct 28 ms 70492 KB Output is correct
3 Correct 34 ms 70524 KB Output is correct
4 Correct 28 ms 70444 KB Output is correct
5 Correct 29 ms 70508 KB Output is correct
6 Correct 29 ms 70492 KB Output is correct
7 Correct 29 ms 70484 KB Output is correct
8 Correct 28 ms 70472 KB Output is correct
9 Correct 28 ms 70520 KB Output is correct
10 Correct 28 ms 70464 KB Output is correct
11 Correct 29 ms 70480 KB Output is correct
12 Correct 30 ms 70488 KB Output is correct
13 Correct 30 ms 70512 KB Output is correct
14 Correct 28 ms 70492 KB Output is correct
15 Correct 28 ms 70484 KB Output is correct
16 Correct 28 ms 70424 KB Output is correct
17 Correct 29 ms 70540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70524 KB Output is correct
2 Correct 28 ms 70468 KB Output is correct
3 Correct 663 ms 127440 KB Output is correct
4 Correct 658 ms 132292 KB Output is correct
5 Correct 444 ms 116896 KB Output is correct
6 Correct 452 ms 114624 KB Output is correct
7 Correct 445 ms 117068 KB Output is correct
8 Correct 687 ms 130348 KB Output is correct
9 Correct 552 ms 127988 KB Output is correct
10 Correct 708 ms 133332 KB Output is correct
11 Correct 541 ms 124000 KB Output is correct
12 Correct 371 ms 116004 KB Output is correct
13 Correct 617 ms 140336 KB Output is correct
14 Correct 389 ms 112100 KB Output is correct
15 Correct 389 ms 115312 KB Output is correct
16 Correct 334 ms 116656 KB Output is correct
17 Correct 361 ms 114672 KB Output is correct
18 Correct 729 ms 134308 KB Output is correct
19 Correct 45 ms 72664 KB Output is correct
20 Correct 197 ms 92712 KB Output is correct
21 Correct 292 ms 122084 KB Output is correct
22 Correct 267 ms 114048 KB Output is correct
23 Correct 566 ms 122796 KB Output is correct
24 Correct 288 ms 116948 KB Output is correct
25 Correct 326 ms 118428 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 94488 KB Output is correct
2 Correct 967 ms 140988 KB Output is correct
3 Correct 1002 ms 144640 KB Output is correct
4 Correct 1063 ms 157696 KB Output is correct
5 Correct 1407 ms 160420 KB Output is correct
6 Correct 1372 ms 157328 KB Output is correct
7 Correct 470 ms 122148 KB Output is correct
8 Correct 285 ms 120268 KB Output is correct
9 Correct 1173 ms 155964 KB Output is correct
10 Correct 516 ms 135380 KB Output is correct
11 Correct 53 ms 76508 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 94488 KB Output is correct
2 Correct 967 ms 140988 KB Output is correct
3 Correct 1002 ms 144640 KB Output is correct
4 Correct 1063 ms 157696 KB Output is correct
5 Correct 1407 ms 160420 KB Output is correct
6 Correct 1372 ms 157328 KB Output is correct
7 Correct 470 ms 122148 KB Output is correct
8 Correct 285 ms 120268 KB Output is correct
9 Correct 1173 ms 155964 KB Output is correct
10 Correct 516 ms 135380 KB Output is correct
11 Correct 53 ms 76508 KB Output is correct
12 Correct 1028 ms 143608 KB Output is correct
13 Correct 1002 ms 148820 KB Output is correct
14 Correct 1468 ms 151836 KB Output is correct
15 Correct 716 ms 140380 KB Output is correct
16 Correct 844 ms 137980 KB Output is correct
17 Correct 939 ms 148660 KB Output is correct
18 Correct 737 ms 140360 KB Output is correct
19 Correct 846 ms 138020 KB Output is correct
20 Correct 604 ms 112928 KB Output is correct
21 Correct 127 ms 82984 KB Output is correct
22 Correct 609 ms 130592 KB Output is correct
23 Correct 535 ms 126800 KB Output is correct
24 Correct 429 ms 114532 KB Output is correct
25 Correct 480 ms 123064 KB Output is correct
26 Correct 346 ms 106076 KB Output is correct
27 Correct 1607 ms 155048 KB Output is correct
28 Correct 828 ms 146900 KB Output is correct
29 Correct 1442 ms 148492 KB Output is correct
30 Correct 559 ms 114192 KB Output is correct
31 Correct 1289 ms 147876 KB Output is correct
32 Correct 395 ms 126508 KB Output is correct
33 Correct 388 ms 122180 KB Output is correct
34 Correct 506 ms 126456 KB Output is correct
35 Correct 476 ms 125052 KB Output is correct
36 Correct 374 ms 119536 KB Output is correct
37 Correct 283 ms 119208 KB Output is correct
38 Correct 267 ms 110904 KB Output is correct
39 Correct 549 ms 119880 KB Output is correct
40 Correct 291 ms 114036 KB Output is correct
41 Correct 315 ms 115804 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 70444 KB Output is correct
2 Correct 28 ms 70492 KB Output is correct
3 Correct 34 ms 70524 KB Output is correct
4 Correct 28 ms 70444 KB Output is correct
5 Correct 29 ms 70508 KB Output is correct
6 Correct 29 ms 70492 KB Output is correct
7 Correct 29 ms 70484 KB Output is correct
8 Correct 28 ms 70472 KB Output is correct
9 Correct 28 ms 70520 KB Output is correct
10 Correct 28 ms 70464 KB Output is correct
11 Correct 29 ms 70480 KB Output is correct
12 Correct 30 ms 70488 KB Output is correct
13 Correct 30 ms 70512 KB Output is correct
14 Correct 28 ms 70492 KB Output is correct
15 Correct 28 ms 70484 KB Output is correct
16 Correct 28 ms 70424 KB Output is correct
17 Correct 29 ms 70540 KB Output is correct
18 Correct 28 ms 70524 KB Output is correct
19 Correct 28 ms 70468 KB Output is correct
20 Correct 663 ms 127440 KB Output is correct
21 Correct 658 ms 132292 KB Output is correct
22 Correct 444 ms 116896 KB Output is correct
23 Correct 452 ms 114624 KB Output is correct
24 Correct 445 ms 117068 KB Output is correct
25 Correct 687 ms 130348 KB Output is correct
26 Correct 552 ms 127988 KB Output is correct
27 Correct 708 ms 133332 KB Output is correct
28 Correct 541 ms 124000 KB Output is correct
29 Correct 371 ms 116004 KB Output is correct
30 Correct 617 ms 140336 KB Output is correct
31 Correct 389 ms 112100 KB Output is correct
32 Correct 389 ms 115312 KB Output is correct
33 Correct 334 ms 116656 KB Output is correct
34 Correct 361 ms 114672 KB Output is correct
35 Correct 729 ms 134308 KB Output is correct
36 Correct 45 ms 72664 KB Output is correct
37 Correct 197 ms 92712 KB Output is correct
38 Correct 292 ms 122084 KB Output is correct
39 Correct 267 ms 114048 KB Output is correct
40 Correct 566 ms 122796 KB Output is correct
41 Correct 288 ms 116948 KB Output is correct
42 Correct 326 ms 118428 KB Output is correct
43 Correct 186 ms 94488 KB Output is correct
44 Correct 967 ms 140988 KB Output is correct
45 Correct 1002 ms 144640 KB Output is correct
46 Correct 1063 ms 157696 KB Output is correct
47 Correct 1407 ms 160420 KB Output is correct
48 Correct 1372 ms 157328 KB Output is correct
49 Correct 470 ms 122148 KB Output is correct
50 Correct 285 ms 120268 KB Output is correct
51 Correct 1173 ms 155964 KB Output is correct
52 Correct 516 ms 135380 KB Output is correct
53 Correct 53 ms 76508 KB Output is correct
54 Correct 1028 ms 143608 KB Output is correct
55 Correct 1002 ms 148820 KB Output is correct
56 Correct 1468 ms 151836 KB Output is correct
57 Correct 716 ms 140380 KB Output is correct
58 Correct 844 ms 137980 KB Output is correct
59 Correct 939 ms 148660 KB Output is correct
60 Correct 737 ms 140360 KB Output is correct
61 Correct 846 ms 138020 KB Output is correct
62 Correct 604 ms 112928 KB Output is correct
63 Correct 127 ms 82984 KB Output is correct
64 Correct 609 ms 130592 KB Output is correct
65 Correct 535 ms 126800 KB Output is correct
66 Correct 429 ms 114532 KB Output is correct
67 Correct 480 ms 123064 KB Output is correct
68 Correct 346 ms 106076 KB Output is correct
69 Correct 1607 ms 155048 KB Output is correct
70 Correct 828 ms 146900 KB Output is correct
71 Correct 1442 ms 148492 KB Output is correct
72 Correct 559 ms 114192 KB Output is correct
73 Correct 1289 ms 147876 KB Output is correct
74 Correct 395 ms 126508 KB Output is correct
75 Correct 388 ms 122180 KB Output is correct
76 Correct 506 ms 126456 KB Output is correct
77 Correct 476 ms 125052 KB Output is correct
78 Correct 374 ms 119536 KB Output is correct
79 Correct 283 ms 119208 KB Output is correct
80 Correct 267 ms 110904 KB Output is correct
81 Correct 549 ms 119880 KB Output is correct
82 Correct 291 ms 114036 KB Output is correct
83 Correct 315 ms 115804 KB Output is correct
84 Correct 163 ms 89328 KB Output is correct
85 Correct 1103 ms 148480 KB Output is correct
86 Correct 1836 ms 174324 KB Output is correct
87 Correct 111 ms 89864 KB Output is correct
88 Correct 154 ms 86704 KB Output is correct
89 Correct 112 ms 89860 KB Output is correct
90 Correct 68 ms 76616 KB Output is correct
91 Correct 30 ms 70676 KB Output is correct
92 Correct 65 ms 73884 KB Output is correct
93 Correct 463 ms 104388 KB Output is correct
94 Correct 129 ms 85176 KB Output is correct
95 Correct 700 ms 137480 KB Output is correct
96 Correct 585 ms 131084 KB Output is correct
97 Correct 468 ms 119216 KB Output is correct
98 Correct 521 ms 126636 KB Output is correct
99 Correct 2289 ms 199188 KB Output is correct
100 Correct 1133 ms 153428 KB Output is correct
101 Correct 1699 ms 167584 KB Output is correct
102 Correct 592 ms 117292 KB Output is correct
103 Correct 421 ms 122196 KB Output is correct
104 Correct 414 ms 120680 KB Output is correct
105 Correct 537 ms 124968 KB Output is correct
106 Correct 465 ms 121708 KB Output is correct
107 Correct 454 ms 119596 KB Output is correct
108 Correct 103 ms 77028 KB Output is correct
109 Correct 1065 ms 136688 KB Output is correct
110 Correct 937 ms 150652 KB Output is correct
111 Correct 861 ms 150192 KB Output is correct
112 Correct 517 ms 124816 KB Output is correct
113 Correct 460 ms 121188 KB Output is correct