Submission #625553

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625553	2022-08-10T14:45:34 Z	timmyfeng	Radio Towers (IOI22_towers)	C++17	100 / 100	2384 ms	101648 KB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<ordered_set<pair<int, int>>> settree;
vector<int> min_h, max_h, up, down, h;
int n;

void build(int u, int l, int r) {
	if (l + 1 == r) {
		min_h[u] = max_h[u] = h[l];
	} else {
		int m = (l + r) / 2;

		build(2 * u, l, m);
		build(2 * u + 1, m, r);

		min_h[u] = min(min_h[2 * u], min_h[2 * u + 1]);
		max_h[u] = max(max_h[2 * u], max_h[2 * u + 1]);
		up[u] = max({up[2 * u], up[2 * u + 1], max_h[2 * u + 1] - min_h[2 * u]});
		down[u] = max({down[2 * u], down[2 * u + 1], max_h[2 * u] - min_h[2 * u + 1]});
	}
}

void update(int a, int x, int u = 1, int l = 0, int r = n) {
	if (l + 1 < r) {
		int m = (l + r) / 2;
		if (a < m) update(a, x, 2 * u, l, m);
		else update(a, x, 2 * u + 1, m, r);
	}
	settree[u].insert({x, a});
}

void init(int n, vector<int> h) {
	::h = h, ::n = n;

	vector<pair<int, int>> points;
	for (int i = 0; i < n; ++i) {
		points.push_back({h[i], i});
	}

	sort(points.begin(), points.end());

	settree.resize(4 * n);

	set<array<int, 3>> ranges = {{INT_MIN, INT_MIN, -1}, {INT_MAX, INT_MAX, -1}};
	for (auto [hi, i] : points) {
		auto nxt = ranges.upper_bound({i, i, hi});
		auto prv = nxt; --prv;

		if (nxt->at(0) == i + 1 && prv->at(1) == i - 1) {
			update(i, hi - max(nxt->at(2), prv->at(2)));
		}

		int l = i, r = i, x = hi;
		if (nxt->at(0) == i + 1) {
			r = nxt->at(1);
			x = min(x, nxt->at(2));
			ranges.erase(nxt);
		}
		if (prv->at(1) == i - 1) {
			l = prv->at(0);
			x = min(x, prv->at(2));
			ranges.erase(prv);
		}
		
		ranges.insert({l, r, x});
	}

	max_h.resize(4 * n);
	min_h.resize(4 * n);
	up.resize(4 * n);
	down.resize(4 * n);

	build(1, 0, n);
}

int find_first(int a, int d, int &prefix, int u = 1, int l = 0, int r = n) {
	if (r <= a) return n;
	if (l + 1 == r) {
		if (h[l] - prefix >= d) return l;
		prefix = min(prefix, min_h[u]);
		return n;
	}

	if (l >= a && up[u] < d && max_h[u] - prefix < d) {
		prefix = min(prefix, min_h[u]);
		return n;
	}

	int m = (l + r) / 2;
	int b = find_first(a, d, prefix, 2 * u, l, m);
	return b == n ? find_first(a, d, prefix, 2 * u + 1, m, r) : b;
}

int find_last(int b, int d, int &suffix, int u = 1, int l = 0, int r = n) {
	if (l > b) return -1;
	if (l + 1 == r) {
		if (h[l] - suffix >= d) return l;
		suffix = min(suffix, min_h[u]);
		return -1;
	}

	if (r <= b + 1 && down[u] < d && max_h[u] - suffix < d) {
		suffix = min(suffix, min_h[u]);
		return -1;
	}

	int m = (l + r) / 2;
	int a = find_last(b, d, suffix, 2 * u + 1, m, r);
	return a == -1 ? find_last(b, d, suffix, 2 * u, l, m) : a;
}

int query(int a, int b, int d, int u = 1, int l = 0, int r = n) {
	if (a >= b || b <= l || r <= a) return 0;
	if (a <= l && r <= b) return settree[u].size() - settree[u].order_of_key({d, -1});
	int m = (l + r) / 2;
	return query(a, b, d, 2 * u, l, m) + query(a, b, d, 2 * u + 1, m, r);
}

int max_towers(int l, int r, int d) {
	int temp = h[l];
	l = find_first(l, d, temp);
	temp = h[r];
	r = find_last(r, d, temp);

	return 1 + query(l, r + 1, d);
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	27544 KB	Output is correct
2	Correct	823 ms	46016 KB	Output is correct
3	Correct	1020 ms	45984 KB	Output is correct
4	Correct	963 ms	46096 KB	Output is correct
5	Correct	933 ms	46092 KB	Output is correct
6	Correct	872 ms	46060 KB	Output is correct
7	Correct	942 ms	45988 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	1 ms	1104 KB	Output is correct
10	Correct	1 ms	1104 KB	Output is correct

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	464 KB	Output is correct
2	Correct	3 ms	1616 KB	Output is correct
3	Correct	3 ms	1616 KB	Output is correct
4	Correct	4 ms	1872 KB	Output is correct
5	Correct	4 ms	1872 KB	Output is correct
6	Correct	4 ms	1872 KB	Output is correct
7	Correct	4 ms	1872 KB	Output is correct
8	Correct	1 ms	1104 KB	Output is correct
9	Correct	1 ms	1104 KB	Output is correct
10	Correct	1 ms	1104 KB	Output is correct
11	Correct	2 ms	1104 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	1 ms	1104 KB	Output is correct
14	Correct	1 ms	1104 KB	Output is correct
15	Correct	3 ms	1616 KB	Output is correct
16	Correct	4 ms	1872 KB	Output is correct
17	Correct	4 ms	1872 KB	Output is correct
18	Correct	2 ms	1232 KB	Output is correct
19	Correct	2 ms	1104 KB	Output is correct
20	Correct	3 ms	1616 KB	Output is correct
21	Correct	4 ms	1976 KB	Output is correct
22	Correct	4 ms	1872 KB	Output is correct
23	Correct	1 ms	1104 KB	Output is correct
24	Correct	1 ms	1104 KB	Output is correct
25	Correct	2 ms	848 KB	Output is correct
26	Correct	3 ms	1616 KB	Output is correct
27	Correct	3 ms	1616 KB	Output is correct
28	Correct	4 ms	1872 KB	Output is correct
29	Correct	4 ms	1872 KB	Output is correct
30	Correct	5 ms	1872 KB	Output is correct
31	Correct	4 ms	1872 KB	Output is correct
32	Correct	1 ms	1104 KB	Output is correct
33	Correct	1 ms	1156 KB	Output is correct
34	Correct	2 ms	1104 KB	Output is correct
35	Correct	1 ms	1104 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	464 KB	Output is correct
2	Correct	3 ms	1616 KB	Output is correct
3	Correct	3 ms	1616 KB	Output is correct
4	Correct	4 ms	1872 KB	Output is correct
5	Correct	4 ms	1872 KB	Output is correct
6	Correct	4 ms	1872 KB	Output is correct
7	Correct	4 ms	1872 KB	Output is correct
8	Correct	1 ms	1104 KB	Output is correct
9	Correct	1 ms	1104 KB	Output is correct
10	Correct	1 ms	1104 KB	Output is correct
11	Correct	2 ms	1104 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	1 ms	1104 KB	Output is correct
14	Correct	1 ms	1104 KB	Output is correct
15	Correct	3 ms	1616 KB	Output is correct
16	Correct	4 ms	1872 KB	Output is correct
17	Correct	4 ms	1872 KB	Output is correct
18	Correct	2 ms	1232 KB	Output is correct
19	Correct	2 ms	1104 KB	Output is correct
20	Correct	3 ms	1616 KB	Output is correct
21	Correct	4 ms	1976 KB	Output is correct
22	Correct	4 ms	1872 KB	Output is correct
23	Correct	1 ms	1104 KB	Output is correct
24	Correct	1 ms	1104 KB	Output is correct
25	Correct	2 ms	848 KB	Output is correct
26	Correct	3 ms	1616 KB	Output is correct
27	Correct	3 ms	1616 KB	Output is correct
28	Correct	4 ms	1872 KB	Output is correct
29	Correct	4 ms	1872 KB	Output is correct
30	Correct	5 ms	1872 KB	Output is correct
31	Correct	4 ms	1872 KB	Output is correct
32	Correct	1 ms	1104 KB	Output is correct
33	Correct	1 ms	1156 KB	Output is correct
34	Correct	2 ms	1104 KB	Output is correct
35	Correct	1 ms	1104 KB	Output is correct
36	Correct	240 ms	53060 KB	Output is correct
37	Correct	442 ms	83068 KB	Output is correct
38	Correct	432 ms	82908 KB	Output is correct
39	Correct	640 ms	101388 KB	Output is correct
40	Correct	640 ms	101372 KB	Output is correct
41	Correct	631 ms	101384 KB	Output is correct
42	Correct	629 ms	101372 KB	Output is correct
43	Correct	53 ms	46216 KB	Output is correct
44	Correct	52 ms	46032 KB	Output is correct
45	Correct	50 ms	46036 KB	Output is correct
46	Correct	50 ms	46068 KB	Output is correct
47	Correct	423 ms	82940 KB	Output is correct
48	Correct	640 ms	101472 KB	Output is correct
49	Correct	648 ms	101456 KB	Output is correct
50	Correct	52 ms	45972 KB	Output is correct
51	Correct	53 ms	46132 KB	Output is correct
52	Correct	414 ms	82960 KB	Output is correct
53	Correct	657 ms	101400 KB	Output is correct
54	Correct	634 ms	101404 KB	Output is correct
55	Correct	51 ms	46100 KB	Output is correct
56	Correct	50 ms	46012 KB	Output is correct
57	Correct	406 ms	80092 KB	Output is correct
58	Correct	417 ms	83196 KB	Output is correct
59	Correct	418 ms	83132 KB	Output is correct
60	Correct	634 ms	101424 KB	Output is correct
61	Correct	631 ms	101464 KB	Output is correct
62	Correct	640 ms	101524 KB	Output is correct
63	Correct	651 ms	101648 KB	Output is correct
64	Correct	50 ms	45984 KB	Output is correct
65	Correct	49 ms	46092 KB	Output is correct
66	Correct	49 ms	46012 KB	Output is correct
67	Correct	50 ms	46100 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1286 ms	82272 KB	Output is correct
2	Correct	1649 ms	82956 KB	Output is correct
3	Correct	1586 ms	83016 KB	Output is correct
4	Correct	1671 ms	101356 KB	Output is correct
5	Correct	1706 ms	101412 KB	Output is correct
6	Correct	1934 ms	101460 KB	Output is correct
7	Correct	1813 ms	101404 KB	Output is correct
8	Correct	833 ms	46096 KB	Output is correct
9	Correct	1004 ms	46012 KB	Output is correct
10	Correct	902 ms	46088 KB	Output is correct
11	Correct	1031 ms	46224 KB	Output is correct
12	Correct	1002 ms	46012 KB	Output is correct
13	Correct	813 ms	46096 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	1104 KB	Output is correct
16	Correct	1 ms	1104 KB	Output is correct
17	Correct	413 ms	82900 KB	Output is correct
18	Correct	632 ms	101380 KB	Output is correct
19	Correct	637 ms	101464 KB	Output is correct
20	Correct	58 ms	46092 KB	Output is correct
21	Correct	59 ms	45988 KB	Output is correct
22	Correct	418 ms	82928 KB	Output is correct
23	Correct	644 ms	101404 KB	Output is correct
24	Correct	644 ms	101460 KB	Output is correct
25	Correct	50 ms	45972 KB	Output is correct
26	Correct	51 ms	46100 KB	Output is correct
27	Correct	3 ms	1616 KB	Output is correct
28	Correct	4 ms	1872 KB	Output is correct
29	Correct	4 ms	1972 KB	Output is correct
30	Correct	1 ms	1104 KB	Output is correct
31	Correct	1 ms	1232 KB	Output is correct
32	Correct	3 ms	1616 KB	Output is correct
33	Correct	4 ms	1872 KB	Output is correct
34	Correct	4 ms	1872 KB	Output is correct
35	Correct	1 ms	1104 KB	Output is correct
36	Correct	1 ms	1232 KB	Output is correct

Subtask #5
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	434 ms	19068 KB	Output is correct
2	Correct	1798 ms	83004 KB	Output is correct
3	Correct	2149 ms	82956 KB	Output is correct
4	Correct	2268 ms	101448 KB	Output is correct
5	Correct	2033 ms	101432 KB	Output is correct
6	Correct	2206 ms	101436 KB	Output is correct
7	Correct	2180 ms	101436 KB	Output is correct
8	Correct	921 ms	46104 KB	Output is correct
9	Correct	803 ms	46012 KB	Output is correct
10	Correct	856 ms	46044 KB	Output is correct
11	Correct	958 ms	46092 KB	Output is correct
12	Correct	423 ms	82960 KB	Output is correct
13	Correct	623 ms	101436 KB	Output is correct
14	Correct	644 ms	101492 KB	Output is correct
15	Correct	51 ms	46092 KB	Output is correct
16	Correct	49 ms	46092 KB	Output is correct
17	Correct	424 ms	80120 KB	Output is correct
18	Correct	425 ms	83012 KB	Output is correct
19	Correct	424 ms	83084 KB	Output is correct
20	Correct	644 ms	101460 KB	Output is correct
21	Correct	641 ms	101412 KB	Output is correct
22	Correct	631 ms	101404 KB	Output is correct
23	Correct	632 ms	101372 KB	Output is correct
24	Correct	56 ms	45984 KB	Output is correct
25	Correct	54 ms	45996 KB	Output is correct
26	Correct	50 ms	46024 KB	Output is correct
27	Correct	52 ms	46024 KB	Output is correct
28	Correct	3 ms	1616 KB	Output is correct
29	Correct	3 ms	1872 KB	Output is correct
30	Correct	4 ms	1872 KB	Output is correct
31	Correct	1 ms	1104 KB	Output is correct
32	Correct	2 ms	1232 KB	Output is correct
33	Correct	1 ms	848 KB	Output is correct
34	Correct	3 ms	1704 KB	Output is correct
35	Correct	3 ms	1616 KB	Output is correct
36	Correct	4 ms	1872 KB	Output is correct
37	Correct	4 ms	1888 KB	Output is correct
38	Correct	4 ms	1872 KB	Output is correct
39	Correct	4 ms	1872 KB	Output is correct
40	Correct	2 ms	1104 KB	Output is correct
41	Correct	1 ms	1104 KB	Output is correct
42	Correct	1 ms	1104 KB	Output is correct
43	Correct	1 ms	1104 KB	Output is correct

Subtask #6
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	464 KB	Output is correct
2	Correct	3 ms	1616 KB	Output is correct
3	Correct	3 ms	1616 KB	Output is correct
4	Correct	4 ms	1872 KB	Output is correct
5	Correct	4 ms	1872 KB	Output is correct
6	Correct	4 ms	1872 KB	Output is correct
7	Correct	4 ms	1872 KB	Output is correct
8	Correct	1 ms	1104 KB	Output is correct
9	Correct	1 ms	1104 KB	Output is correct
10	Correct	1 ms	1104 KB	Output is correct
11	Correct	2 ms	1104 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	1 ms	1104 KB	Output is correct
14	Correct	1 ms	1104 KB	Output is correct
15	Correct	3 ms	1616 KB	Output is correct
16	Correct	4 ms	1872 KB	Output is correct
17	Correct	4 ms	1872 KB	Output is correct
18	Correct	2 ms	1232 KB	Output is correct
19	Correct	2 ms	1104 KB	Output is correct
20	Correct	3 ms	1616 KB	Output is correct
21	Correct	4 ms	1976 KB	Output is correct
22	Correct	4 ms	1872 KB	Output is correct
23	Correct	1 ms	1104 KB	Output is correct
24	Correct	1 ms	1104 KB	Output is correct
25	Correct	2 ms	848 KB	Output is correct
26	Correct	3 ms	1616 KB	Output is correct
27	Correct	3 ms	1616 KB	Output is correct
28	Correct	4 ms	1872 KB	Output is correct
29	Correct	4 ms	1872 KB	Output is correct
30	Correct	5 ms	1872 KB	Output is correct
31	Correct	4 ms	1872 KB	Output is correct
32	Correct	1 ms	1104 KB	Output is correct
33	Correct	1 ms	1156 KB	Output is correct
34	Correct	2 ms	1104 KB	Output is correct
35	Correct	1 ms	1104 KB	Output is correct
36	Correct	240 ms	53060 KB	Output is correct
37	Correct	442 ms	83068 KB	Output is correct
38	Correct	432 ms	82908 KB	Output is correct
39	Correct	640 ms	101388 KB	Output is correct
40	Correct	640 ms	101372 KB	Output is correct
41	Correct	631 ms	101384 KB	Output is correct
42	Correct	629 ms	101372 KB	Output is correct
43	Correct	53 ms	46216 KB	Output is correct
44	Correct	52 ms	46032 KB	Output is correct
45	Correct	50 ms	46036 KB	Output is correct
46	Correct	50 ms	46068 KB	Output is correct
47	Correct	423 ms	82940 KB	Output is correct
48	Correct	640 ms	101472 KB	Output is correct
49	Correct	648 ms	101456 KB	Output is correct
50	Correct	52 ms	45972 KB	Output is correct
51	Correct	53 ms	46132 KB	Output is correct
52	Correct	414 ms	82960 KB	Output is correct
53	Correct	657 ms	101400 KB	Output is correct
54	Correct	634 ms	101404 KB	Output is correct
55	Correct	51 ms	46100 KB	Output is correct
56	Correct	50 ms	46012 KB	Output is correct
57	Correct	406 ms	80092 KB	Output is correct
58	Correct	417 ms	83196 KB	Output is correct
59	Correct	418 ms	83132 KB	Output is correct
60	Correct	634 ms	101424 KB	Output is correct
61	Correct	631 ms	101464 KB	Output is correct
62	Correct	640 ms	101524 KB	Output is correct
63	Correct	651 ms	101648 KB	Output is correct
64	Correct	50 ms	45984 KB	Output is correct
65	Correct	49 ms	46092 KB	Output is correct
66	Correct	49 ms	46012 KB	Output is correct
67	Correct	50 ms	46100 KB	Output is correct
68	Correct	1286 ms	82272 KB	Output is correct
69	Correct	1649 ms	82956 KB	Output is correct
70	Correct	1586 ms	83016 KB	Output is correct
71	Correct	1671 ms	101356 KB	Output is correct
72	Correct	1706 ms	101412 KB	Output is correct
73	Correct	1934 ms	101460 KB	Output is correct
74	Correct	1813 ms	101404 KB	Output is correct
75	Correct	833 ms	46096 KB	Output is correct
76	Correct	1004 ms	46012 KB	Output is correct
77	Correct	902 ms	46088 KB	Output is correct
78	Correct	1031 ms	46224 KB	Output is correct
79	Correct	1002 ms	46012 KB	Output is correct
80	Correct	813 ms	46096 KB	Output is correct
81	Correct	0 ms	208 KB	Output is correct
82	Correct	1 ms	1104 KB	Output is correct
83	Correct	1 ms	1104 KB	Output is correct
84	Correct	413 ms	82900 KB	Output is correct
85	Correct	632 ms	101380 KB	Output is correct
86	Correct	637 ms	101464 KB	Output is correct
87	Correct	58 ms	46092 KB	Output is correct
88	Correct	59 ms	45988 KB	Output is correct
89	Correct	418 ms	82928 KB	Output is correct
90	Correct	644 ms	101404 KB	Output is correct
91	Correct	644 ms	101460 KB	Output is correct
92	Correct	50 ms	45972 KB	Output is correct
93	Correct	51 ms	46100 KB	Output is correct
94	Correct	3 ms	1616 KB	Output is correct
95	Correct	4 ms	1872 KB	Output is correct
96	Correct	4 ms	1972 KB	Output is correct
97	Correct	1 ms	1104 KB	Output is correct
98	Correct	1 ms	1232 KB	Output is correct
99	Correct	3 ms	1616 KB	Output is correct
100	Correct	4 ms	1872 KB	Output is correct
101	Correct	4 ms	1872 KB	Output is correct
102	Correct	1 ms	1104 KB	Output is correct
103	Correct	1 ms	1232 KB	Output is correct
104	Correct	1501 ms	73528 KB	Output is correct
105	Correct	1764 ms	82888 KB	Output is correct
106	Correct	1866 ms	83200 KB	Output is correct
107	Correct	1994 ms	101488 KB	Output is correct
108	Correct	2000 ms	101420 KB	Output is correct
109	Correct	2095 ms	101432 KB	Output is correct
110	Correct	1850 ms	101572 KB	Output is correct
111	Correct	1000 ms	45976 KB	Output is correct
112	Correct	1002 ms	46100 KB	Output is correct
113	Correct	1010 ms	46012 KB	Output is correct
114	Correct	997 ms	46012 KB	Output is correct

Subtask #7
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	27544 KB	Output is correct
2	Correct	823 ms	46016 KB	Output is correct
3	Correct	1020 ms	45984 KB	Output is correct
4	Correct	963 ms	46096 KB	Output is correct
5	Correct	933 ms	46092 KB	Output is correct
6	Correct	872 ms	46060 KB	Output is correct
7	Correct	942 ms	45988 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	1 ms	1104 KB	Output is correct
10	Correct	1 ms	1104 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	3 ms	1616 KB	Output is correct
13	Correct	3 ms	1616 KB	Output is correct
14	Correct	4 ms	1872 KB	Output is correct
15	Correct	4 ms	1872 KB	Output is correct
16	Correct	4 ms	1872 KB	Output is correct
17	Correct	4 ms	1872 KB	Output is correct
18	Correct	1 ms	1104 KB	Output is correct
19	Correct	1 ms	1104 KB	Output is correct
20	Correct	1 ms	1104 KB	Output is correct
21	Correct	2 ms	1104 KB	Output is correct
22	Correct	0 ms	208 KB	Output is correct
23	Correct	1 ms	1104 KB	Output is correct
24	Correct	1 ms	1104 KB	Output is correct
25	Correct	3 ms	1616 KB	Output is correct
26	Correct	4 ms	1872 KB	Output is correct
27	Correct	4 ms	1872 KB	Output is correct
28	Correct	2 ms	1232 KB	Output is correct
29	Correct	2 ms	1104 KB	Output is correct
30	Correct	3 ms	1616 KB	Output is correct
31	Correct	4 ms	1976 KB	Output is correct
32	Correct	4 ms	1872 KB	Output is correct
33	Correct	1 ms	1104 KB	Output is correct
34	Correct	1 ms	1104 KB	Output is correct
35	Correct	2 ms	848 KB	Output is correct
36	Correct	3 ms	1616 KB	Output is correct
37	Correct	3 ms	1616 KB	Output is correct
38	Correct	4 ms	1872 KB	Output is correct
39	Correct	4 ms	1872 KB	Output is correct
40	Correct	5 ms	1872 KB	Output is correct
41	Correct	4 ms	1872 KB	Output is correct
42	Correct	1 ms	1104 KB	Output is correct
43	Correct	1 ms	1156 KB	Output is correct
44	Correct	2 ms	1104 KB	Output is correct
45	Correct	1 ms	1104 KB	Output is correct
46	Correct	240 ms	53060 KB	Output is correct
47	Correct	442 ms	83068 KB	Output is correct
48	Correct	432 ms	82908 KB	Output is correct
49	Correct	640 ms	101388 KB	Output is correct
50	Correct	640 ms	101372 KB	Output is correct
51	Correct	631 ms	101384 KB	Output is correct
52	Correct	629 ms	101372 KB	Output is correct
53	Correct	53 ms	46216 KB	Output is correct
54	Correct	52 ms	46032 KB	Output is correct
55	Correct	50 ms	46036 KB	Output is correct
56	Correct	50 ms	46068 KB	Output is correct
57	Correct	423 ms	82940 KB	Output is correct
58	Correct	640 ms	101472 KB	Output is correct
59	Correct	648 ms	101456 KB	Output is correct
60	Correct	52 ms	45972 KB	Output is correct
61	Correct	53 ms	46132 KB	Output is correct
62	Correct	414 ms	82960 KB	Output is correct
63	Correct	657 ms	101400 KB	Output is correct
64	Correct	634 ms	101404 KB	Output is correct
65	Correct	51 ms	46100 KB	Output is correct
66	Correct	50 ms	46012 KB	Output is correct
67	Correct	406 ms	80092 KB	Output is correct
68	Correct	417 ms	83196 KB	Output is correct
69	Correct	418 ms	83132 KB	Output is correct
70	Correct	634 ms	101424 KB	Output is correct
71	Correct	631 ms	101464 KB	Output is correct
72	Correct	640 ms	101524 KB	Output is correct
73	Correct	651 ms	101648 KB	Output is correct
74	Correct	50 ms	45984 KB	Output is correct
75	Correct	49 ms	46092 KB	Output is correct
76	Correct	49 ms	46012 KB	Output is correct
77	Correct	50 ms	46100 KB	Output is correct
78	Correct	1286 ms	82272 KB	Output is correct
79	Correct	1649 ms	82956 KB	Output is correct
80	Correct	1586 ms	83016 KB	Output is correct
81	Correct	1671 ms	101356 KB	Output is correct
82	Correct	1706 ms	101412 KB	Output is correct
83	Correct	1934 ms	101460 KB	Output is correct
84	Correct	1813 ms	101404 KB	Output is correct
85	Correct	833 ms	46096 KB	Output is correct
86	Correct	1004 ms	46012 KB	Output is correct
87	Correct	902 ms	46088 KB	Output is correct
88	Correct	1031 ms	46224 KB	Output is correct
89	Correct	1002 ms	46012 KB	Output is correct
90	Correct	813 ms	46096 KB	Output is correct
91	Correct	0 ms	208 KB	Output is correct
92	Correct	1 ms	1104 KB	Output is correct
93	Correct	1 ms	1104 KB	Output is correct
94	Correct	413 ms	82900 KB	Output is correct
95	Correct	632 ms	101380 KB	Output is correct
96	Correct	637 ms	101464 KB	Output is correct
97	Correct	58 ms	46092 KB	Output is correct
98	Correct	59 ms	45988 KB	Output is correct
99	Correct	418 ms	82928 KB	Output is correct
100	Correct	644 ms	101404 KB	Output is correct
101	Correct	644 ms	101460 KB	Output is correct
102	Correct	50 ms	45972 KB	Output is correct
103	Correct	51 ms	46100 KB	Output is correct
104	Correct	3 ms	1616 KB	Output is correct
105	Correct	4 ms	1872 KB	Output is correct
106	Correct	4 ms	1972 KB	Output is correct
107	Correct	1 ms	1104 KB	Output is correct
108	Correct	1 ms	1232 KB	Output is correct
109	Correct	3 ms	1616 KB	Output is correct
110	Correct	4 ms	1872 KB	Output is correct
111	Correct	4 ms	1872 KB	Output is correct
112	Correct	1 ms	1104 KB	Output is correct
113	Correct	1 ms	1232 KB	Output is correct
114	Correct	434 ms	19068 KB	Output is correct
115	Correct	1798 ms	83004 KB	Output is correct
116	Correct	2149 ms	82956 KB	Output is correct
117	Correct	2268 ms	101448 KB	Output is correct
118	Correct	2033 ms	101432 KB	Output is correct
119	Correct	2206 ms	101436 KB	Output is correct
120	Correct	2180 ms	101436 KB	Output is correct
121	Correct	921 ms	46104 KB	Output is correct
122	Correct	803 ms	46012 KB	Output is correct
123	Correct	856 ms	46044 KB	Output is correct
124	Correct	958 ms	46092 KB	Output is correct
125	Correct	423 ms	82960 KB	Output is correct
126	Correct	623 ms	101436 KB	Output is correct
127	Correct	644 ms	101492 KB	Output is correct
128	Correct	51 ms	46092 KB	Output is correct
129	Correct	49 ms	46092 KB	Output is correct
130	Correct	424 ms	80120 KB	Output is correct
131	Correct	425 ms	83012 KB	Output is correct
132	Correct	424 ms	83084 KB	Output is correct
133	Correct	644 ms	101460 KB	Output is correct
134	Correct	641 ms	101412 KB	Output is correct
135	Correct	631 ms	101404 KB	Output is correct
136	Correct	632 ms	101372 KB	Output is correct
137	Correct	56 ms	45984 KB	Output is correct
138	Correct	54 ms	45996 KB	Output is correct
139	Correct	50 ms	46024 KB	Output is correct
140	Correct	52 ms	46024 KB	Output is correct
141	Correct	3 ms	1616 KB	Output is correct
142	Correct	3 ms	1872 KB	Output is correct
143	Correct	4 ms	1872 KB	Output is correct
144	Correct	1 ms	1104 KB	Output is correct
145	Correct	2 ms	1232 KB	Output is correct
146	Correct	1 ms	848 KB	Output is correct
147	Correct	3 ms	1704 KB	Output is correct
148	Correct	3 ms	1616 KB	Output is correct
149	Correct	4 ms	1872 KB	Output is correct
150	Correct	4 ms	1888 KB	Output is correct
151	Correct	4 ms	1872 KB	Output is correct
152	Correct	4 ms	1872 KB	Output is correct
153	Correct	2 ms	1104 KB	Output is correct
154	Correct	1 ms	1104 KB	Output is correct
155	Correct	1 ms	1104 KB	Output is correct
156	Correct	1 ms	1104 KB	Output is correct
157	Correct	1501 ms	73528 KB	Output is correct
158	Correct	1764 ms	82888 KB	Output is correct
159	Correct	1866 ms	83200 KB	Output is correct
160	Correct	1994 ms	101488 KB	Output is correct
161	Correct	2000 ms	101420 KB	Output is correct
162	Correct	2095 ms	101432 KB	Output is correct
163	Correct	1850 ms	101572 KB	Output is correct
164	Correct	1000 ms	45976 KB	Output is correct
165	Correct	1002 ms	46100 KB	Output is correct
166	Correct	1010 ms	46012 KB	Output is correct
167	Correct	997 ms	46012 KB	Output is correct
168	Correct	0 ms	208 KB	Output is correct
169	Correct	972 ms	27848 KB	Output is correct
170	Correct	1955 ms	82688 KB	Output is correct
171	Correct	1856 ms	82980 KB	Output is correct
172	Correct	2333 ms	101540 KB	Output is correct
173	Correct	2384 ms	101444 KB	Output is correct
174	Correct	2200 ms	101372 KB	Output is correct
175	Correct	2219 ms	101468 KB	Output is correct
176	Correct	844 ms	45996 KB	Output is correct
177	Correct	891 ms	46100 KB	Output is correct
178	Correct	1020 ms	46096 KB	Output is correct
179	Correct	821 ms	45988 KB	Output is correct

Submission #625553

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 11.0 / 11.0

Subtask #3 12.0 / 12.0

Subtask #4 14.0 / 14.0

Subtask #5 17.0 / 17.0

Subtask #6 19.0 / 19.0

Subtask #7 23.0 / 23.0

Subtask #1
4.0 / 4.0

Subtask #2
11.0 / 11.0

Subtask #3
12.0 / 12.0

Subtask #4
14.0 / 14.0

Subtask #5
17.0 / 17.0

Subtask #6
19.0 / 19.0

Subtask #7
23.0 / 23.0