Submission #382211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
382211	2021-03-26T17:21:46 Z	rainboy	New Home (APIO18_new_home)	C	100 / 100	2768 ms	89692 KB

new_home

/* https://oj.uz/submission/66480 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	300000
#define K	N
#define Q	300000
#define M	(N * 2 + Q)
#define Q_	(N * 3 + K)
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(Q))) */
#define INF	0x3f3f3f3f
#define X	100000000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N + K], gg[N], yy[Q], tt[N * 2 + Q], n, k, q;

int compare_t(int h1, int h2) {
	int type1, type2;

	if (tt[h1] != tt[h2])
		return tt[h1] - tt[h2];
	type1 = h1 < n * 2 ? ((h1 & 1) == 0 ? 1 : -1) : 0;
	type2 = h2 < n * 2 ? ((h2 & 1) == 0 ? 1 : -1) : 0;
	return type2 - type1;
}

int *yy_, *ll_, *rr_, *xx_;

int compare_y(int h1, int h2) {
	return yy_[h1] - yy_[h2];
}

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int zz[1 + N + K], ll[1 + N + K], rr[1 + N + K], ii[1 + N + K], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_(), ii[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = xx[ii[u]] != xx[i] ? xx[ii[u]] - xx[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int yyy[2][Q_], lll[2][Q_], rrr[2][Q_], xxx[2][Q_], q_;

void add_event(int x1, int x2, int l, int r) {
	int y;

	if (x1 == x2 || l > r)
		return;
	y = (x1 + x2) / 2;
	yyy[0][q_] = y, lll[0][q_] = l, rrr[0][q_] = r, xxx[0][q_] = x1;
	yyy[1][q_] = -(y + 1), lll[1][q_] = l, rrr[1][q_] = r, xxx[1][q_] = -x2;
	q_++;
}

int st[N_ * 2], n_;

void update(int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = min(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = min(st[r], x), r--;
	}
}

int query(int i) {
	int x = INF;

	for (i += n_; i > 0; i >>= 1)
		x = min(x, st[i]);
	return x;
}

int main() {
	static int hh[M], hh_[Q_], tr[K], ll1[N + K], ii_[Q], ans[Q];
	int m, g, h, h_, h1, h2, i, i_, t, tmp;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d%d%d", &xx[i], &gg[i], &tt[i << 1 | 0], &tt[i << 1 | 1]), gg[i]--;
	for (h = 0; h < q; h++)
		scanf("%d%d", &yy[h], &tt[n * 2 + h]);
	m = n * 2 + q;
	for (h = 0; h < m; h++)
		hh[h] = h;
	compare = compare_t, sort(hh, 0, m);
	for (g = 0; g < k; g++) {
		xx[n + g] = -INF;
		tr[g] = node(n + g);
	}
	q_ = 0, i_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (h_ >= n * 2) {
			h_ -= n * 2;
			ii_[h_] = i_++;
		} else {
			int l, r;

			i = h_ >> 1, g = gg[i];
			split(tr[g], i);
			l = ii[last(l_)], r = r_ ? ii[first(r_)] : -1;
			if ((h_ & 1) == 0) {
				add_event(xx[l], r == -1 ? INF : xx[r], ll1[l], i_ - 1);
				ll1[l] = ll1[i] = i_;
				tr[g] = merge(merge(l_, node(i)), r_);
			} else {
				add_event(xx[l], xx[i], ll1[l], i_ - 1), add_event(xx[i], r == -1 ? INF : xx[r], ll1[i], i_ - 1);
				ll1[l] = i_;
				tr[g] = merge(l_, r_);
			}
		}
	}
	for (g = 0; g < k; g++)
		add_event(-INF, INF, ll1[n + g], i_ - 1);
	for (h = 0; h < q; h++)
		hh[h] = h;
	for (h_ = 0; h_ < q_; h_++)
		hh_[h_] = h_;
	compare = compare_y;
	yy_ = yy, sort(hh, 0, q);
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (t = 0; t < 2; t++) {
		yy_ = yyy[t], ll_ = lll[t], rr_ = rrr[t], xx_ = xxx[t], sort(hh_, 0, q_);
		memset(st, 0x3f, n_ * 2 * sizeof *st);
		for (h = q - 1, h_ = q_ - 1; h >= 0; h--) {
			while (h_ >= 0 && yy_[hh_[h_]] >= yy[hh[h]]) {
				int h1 = hh_[h_--];

				update(ll_[h1], rr_[h1], xx_[h1]);
			}
			ans[hh[h]] = max(ans[hh[h]], yy[hh[h]] - query(ii_[hh[h]]));
		}
		for (h = 0; h < q; h++)
			yy[h] = -yy[h];
		for (h1 = 0, h2 = q - 1; h1 < h2; h1++, h2--)
			tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h] > X ? -1 : ans[h]);
	return 0;
}

Compilation message

new_home.c: In function 'main':
new_home.c:152:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:154:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  154 |   scanf("%d%d%d%d", &xx[i], &gg[i], &tt[i << 1 | 0], &tt[i << 1 | 1]), gg[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:156:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  156 |   scanf("%d%d", &yy[h], &tt[n * 2 + h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	2 ms	492 KB	Output is correct
15	Correct	2 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	1 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	2 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	2 ms	620 KB	Output is correct
27	Correct	2 ms	492 KB	Output is correct
28	Correct	2 ms	620 KB	Output is correct
29	Correct	2 ms	620 KB	Output is correct
30	Correct	2 ms	492 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	2 ms	492 KB	Output is correct
15	Correct	2 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	1 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	2 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	2 ms	620 KB	Output is correct
27	Correct	2 ms	492 KB	Output is correct
28	Correct	2 ms	620 KB	Output is correct
29	Correct	2 ms	620 KB	Output is correct
30	Correct	2 ms	492 KB	Output is correct
31	Correct	299 ms	12368 KB	Output is correct
32	Correct	135 ms	5484 KB	Output is correct
33	Correct	325 ms	12120 KB	Output is correct
34	Correct	272 ms	12240 KB	Output is correct
35	Correct	307 ms	12140 KB	Output is correct
36	Correct	332 ms	12248 KB	Output is correct
37	Correct	257 ms	12168 KB	Output is correct
38	Correct	261 ms	12012 KB	Output is correct
39	Correct	207 ms	12012 KB	Output is correct
40	Correct	223 ms	12012 KB	Output is correct
41	Correct	214 ms	12268 KB	Output is correct
42	Correct	223 ms	12140 KB	Output is correct
43	Correct	75 ms	5996 KB	Output is correct
44	Correct	219 ms	12268 KB	Output is correct
45	Correct	210 ms	12396 KB	Output is correct
46	Correct	192 ms	11756 KB	Output is correct
47	Correct	154 ms	11372 KB	Output is correct
48	Correct	147 ms	10860 KB	Output is correct
49	Correct	172 ms	11628 KB	Output is correct
50	Correct	185 ms	12012 KB	Output is correct
51	Correct	172 ms	11500 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1020 ms	40804 KB	Output is correct
2	Correct	1432 ms	38192 KB	Output is correct
3	Correct	968 ms	57084 KB	Output is correct
4	Correct	1018 ms	45420 KB	Output is correct
5	Correct	1511 ms	37920 KB	Output is correct
6	Correct	1457 ms	38372 KB	Output is correct
7	Correct	856 ms	57028 KB	Output is correct
8	Correct	902 ms	45396 KB	Output is correct
9	Correct	852 ms	41272 KB	Output is correct
10	Correct	952 ms	38992 KB	Output is correct
11	Correct	848 ms	38348 KB	Output is correct
12	Correct	771 ms	38892 KB	Output is correct

Subtask #4
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1637 ms	47928 KB	Output is correct
2	Correct	868 ms	27116 KB	Output is correct
3	Correct	2134 ms	49260 KB	Output is correct
4	Correct	1266 ms	65900 KB	Output is correct
5	Correct	1392 ms	51836 KB	Output is correct
6	Correct	1454 ms	54252 KB	Output is correct
7	Correct	2237 ms	48608 KB	Output is correct
8	Correct	2124 ms	49092 KB	Output is correct
9	Correct	1164 ms	67176 KB	Output is correct
10	Correct	1316 ms	54124 KB	Output is correct
11	Correct	1438 ms	50924 KB	Output is correct
12	Correct	1595 ms	49668 KB	Output is correct
13	Correct	947 ms	47924 KB	Output is correct
14	Correct	956 ms	47340 KB	Output is correct
15	Correct	1047 ms	48620 KB	Output is correct
16	Correct	1042 ms	49260 KB	Output is correct
17	Correct	1113 ms	48320 KB	Output is correct

Subtask #5
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	2 ms	492 KB	Output is correct
15	Correct	2 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	1 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	2 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	2 ms	620 KB	Output is correct
27	Correct	2 ms	492 KB	Output is correct
28	Correct	2 ms	620 KB	Output is correct
29	Correct	2 ms	620 KB	Output is correct
30	Correct	2 ms	492 KB	Output is correct
31	Correct	299 ms	12368 KB	Output is correct
32	Correct	135 ms	5484 KB	Output is correct
33	Correct	325 ms	12120 KB	Output is correct
34	Correct	272 ms	12240 KB	Output is correct
35	Correct	307 ms	12140 KB	Output is correct
36	Correct	332 ms	12248 KB	Output is correct
37	Correct	257 ms	12168 KB	Output is correct
38	Correct	261 ms	12012 KB	Output is correct
39	Correct	207 ms	12012 KB	Output is correct
40	Correct	223 ms	12012 KB	Output is correct
41	Correct	214 ms	12268 KB	Output is correct
42	Correct	223 ms	12140 KB	Output is correct
43	Correct	75 ms	5996 KB	Output is correct
44	Correct	219 ms	12268 KB	Output is correct
45	Correct	210 ms	12396 KB	Output is correct
46	Correct	192 ms	11756 KB	Output is correct
47	Correct	154 ms	11372 KB	Output is correct
48	Correct	147 ms	10860 KB	Output is correct
49	Correct	172 ms	11628 KB	Output is correct
50	Correct	185 ms	12012 KB	Output is correct
51	Correct	172 ms	11500 KB	Output is correct
52	Correct	201 ms	15348 KB	Output is correct
53	Correct	203 ms	14828 KB	Output is correct
54	Correct	237 ms	12488 KB	Output is correct
55	Correct	211 ms	12780 KB	Output is correct
56	Correct	201 ms	13548 KB	Output is correct
57	Correct	213 ms	12012 KB	Output is correct
58	Correct	212 ms	12652 KB	Output is correct
59	Correct	220 ms	13164 KB	Output is correct
60	Correct	217 ms	12012 KB	Output is correct
61	Correct	68 ms	10988 KB	Output is correct
62	Correct	198 ms	14956 KB	Output is correct
63	Correct	220 ms	13164 KB	Output is correct
64	Correct	230 ms	12652 KB	Output is correct
65	Correct	244 ms	12140 KB	Output is correct
66	Correct	222 ms	11628 KB	Output is correct
67	Correct	128 ms	11116 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	2 ms	492 KB	Output is correct
15	Correct	2 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	1 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	2 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	2 ms	620 KB	Output is correct
27	Correct	2 ms	492 KB	Output is correct
28	Correct	2 ms	620 KB	Output is correct
29	Correct	2 ms	620 KB	Output is correct
30	Correct	2 ms	492 KB	Output is correct
31	Correct	299 ms	12368 KB	Output is correct
32	Correct	135 ms	5484 KB	Output is correct
33	Correct	325 ms	12120 KB	Output is correct
34	Correct	272 ms	12240 KB	Output is correct
35	Correct	307 ms	12140 KB	Output is correct
36	Correct	332 ms	12248 KB	Output is correct
37	Correct	257 ms	12168 KB	Output is correct
38	Correct	261 ms	12012 KB	Output is correct
39	Correct	207 ms	12012 KB	Output is correct
40	Correct	223 ms	12012 KB	Output is correct
41	Correct	214 ms	12268 KB	Output is correct
42	Correct	223 ms	12140 KB	Output is correct
43	Correct	75 ms	5996 KB	Output is correct
44	Correct	219 ms	12268 KB	Output is correct
45	Correct	210 ms	12396 KB	Output is correct
46	Correct	192 ms	11756 KB	Output is correct
47	Correct	154 ms	11372 KB	Output is correct
48	Correct	147 ms	10860 KB	Output is correct
49	Correct	172 ms	11628 KB	Output is correct
50	Correct	185 ms	12012 KB	Output is correct
51	Correct	172 ms	11500 KB	Output is correct
52	Correct	1020 ms	40804 KB	Output is correct
53	Correct	1432 ms	38192 KB	Output is correct
54	Correct	968 ms	57084 KB	Output is correct
55	Correct	1018 ms	45420 KB	Output is correct
56	Correct	1511 ms	37920 KB	Output is correct
57	Correct	1457 ms	38372 KB	Output is correct
58	Correct	856 ms	57028 KB	Output is correct
59	Correct	902 ms	45396 KB	Output is correct
60	Correct	852 ms	41272 KB	Output is correct
61	Correct	952 ms	38992 KB	Output is correct
62	Correct	848 ms	38348 KB	Output is correct
63	Correct	771 ms	38892 KB	Output is correct
64	Correct	1637 ms	47928 KB	Output is correct
65	Correct	868 ms	27116 KB	Output is correct
66	Correct	2134 ms	49260 KB	Output is correct
67	Correct	1266 ms	65900 KB	Output is correct
68	Correct	1392 ms	51836 KB	Output is correct
69	Correct	1454 ms	54252 KB	Output is correct
70	Correct	2237 ms	48608 KB	Output is correct
71	Correct	2124 ms	49092 KB	Output is correct
72	Correct	1164 ms	67176 KB	Output is correct
73	Correct	1316 ms	54124 KB	Output is correct
74	Correct	1438 ms	50924 KB	Output is correct
75	Correct	1595 ms	49668 KB	Output is correct
76	Correct	947 ms	47924 KB	Output is correct
77	Correct	956 ms	47340 KB	Output is correct
78	Correct	1047 ms	48620 KB	Output is correct
79	Correct	1042 ms	49260 KB	Output is correct
80	Correct	1113 ms	48320 KB	Output is correct
81	Correct	201 ms	15348 KB	Output is correct
82	Correct	203 ms	14828 KB	Output is correct
83	Correct	237 ms	12488 KB	Output is correct
84	Correct	211 ms	12780 KB	Output is correct
85	Correct	201 ms	13548 KB	Output is correct
86	Correct	213 ms	12012 KB	Output is correct
87	Correct	212 ms	12652 KB	Output is correct
88	Correct	220 ms	13164 KB	Output is correct
89	Correct	217 ms	12012 KB	Output is correct
90	Correct	68 ms	10988 KB	Output is correct
91	Correct	198 ms	14956 KB	Output is correct
92	Correct	220 ms	13164 KB	Output is correct
93	Correct	230 ms	12652 KB	Output is correct
94	Correct	244 ms	12140 KB	Output is correct
95	Correct	222 ms	11628 KB	Output is correct
96	Correct	128 ms	11116 KB	Output is correct
97	Correct	1588 ms	74860 KB	Output is correct
98	Correct	952 ms	25324 KB	Output is correct
99	Correct	2417 ms	71164 KB	Output is correct
100	Correct	1545 ms	89324 KB	Output is correct
101	Correct	1864 ms	77432 KB	Output is correct
102	Correct	2768 ms	71060 KB	Output is correct
103	Correct	1634 ms	71424 KB	Output is correct
104	Correct	1712 ms	70936 KB	Output is correct
105	Correct	1255 ms	70648 KB	Output is correct
106	Correct	1333 ms	70736 KB	Output is correct
107	Correct	1398 ms	79032 KB	Output is correct
108	Correct	1426 ms	81900 KB	Output is correct
109	Correct	1451 ms	74988 KB	Output is correct
110	Correct	1479 ms	78464 KB	Output is correct
111	Correct	1440 ms	81260 KB	Output is correct
112	Correct	1505 ms	74352 KB	Output is correct
113	Correct	366 ms	66668 KB	Output is correct
114	Correct	1628 ms	89692 KB	Output is correct
115	Correct	1666 ms	80964 KB	Output is correct
116	Correct	1728 ms	78316 KB	Output is correct
117	Correct	1699 ms	74576 KB	Output is correct
118	Correct	1557 ms	72940 KB	Output is correct
119	Correct	955 ms	61932 KB	Output is correct
120	Correct	756 ms	63724 KB	Output is correct
121	Correct	866 ms	67180 KB	Output is correct
122	Correct	832 ms	65004 KB	Output is correct
123	Correct	943 ms	69356 KB	Output is correct
124	Correct	1065 ms	71148 KB	Output is correct
125	Correct	961 ms	68844 KB	Output is correct
126	Correct	1077 ms	71280 KB	Output is correct

Submission #382211

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 23.0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 20.0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
23.0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
20.0 / 20.0