oj.uz

Submission #792794

# Submission time Handle Problem Language Result Execution time Memory
792794 2023-07-25T08:51:14 Z 박영우(#10055) Real Mountains (CCO23_day1problem2) C++17
21 / 25
 5000 ms 163080 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 500
#define INF 1000000020
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000003
struct node {
	int mn;
	int mn2;
	int cnt;
	int mnl, mnr;
	node(int x = 0, int ind = 0) {
		mnl = mnr = ind;
		if (!~x) {
			mn = mn2 = cnt = -1;
			return;
		}
		mn = x;
		mn2 = INF;
		cnt = 1;
	}
};
inline node operator+(node n1, node n2) {
	if (!~n1.cnt) return n2;
	if (!~n2.cnt) return n1;
	node ret;
	ret.mn = min(n1.mn, n2.mn);
	ret.cnt = 0;
	ret.mnl = INF;
	ret.mnr = -INF;
	if (ret.mn == n1.mn) ret.cnt += n1.cnt, ret.mnl = min(ret.mnl, n1.mnl), ret.mnr = max(ret.mnr, n1.mnr);
	else ret.mn2 = min(ret.mn2, n1.mn);
	if (ret.mn == n2.mn) ret.cnt += n2.cnt, ret.mnl = min(ret.mnl, n2.mnl), ret.mnr = max(ret.mnr, n2.mnr);
	else ret.mn2 = min(ret.mn2, n2.mn);
	ret.mn2 = min(ret.mn2, n1.mn2);
	ret.mn2 = min(ret.mn2, n2.mn2);
	return ret;
}
int N;
int H[MAX];
int ch[MAX];
namespace segtree {
	int N;
	node tree[MAX * 4];
	int lazy[MAX * 4];
	void init(int s, int e, int loc = 1) {
		lazy[loc] = -1;
		if (s == e) {
			tree[loc] = node(H[s], s);
			return;
		}
		int m = s + e >> 1;
		init(s, m, loc * 2);
		init(m + 1, e, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	inline void prop(int loc) {
		for (auto c : { loc * 2, loc * 2 + 1 }) {
			tree[c].mn = max(tree[c].mn, lazy[loc]);
			lazy[c] = max(lazy[c], lazy[loc]);
			assert(tree[c].mn < tree[c].mn2);
		}
		lazy[loc] = -1;
	}
	inline void upd(int s, int e, int l, int r, int v, int loc = 1) {
		if (s != e) prop(loc);
		if (e < l || r < s) return;
		if (l <= s && e <= r) {
			if (v < tree[loc].mn2) {
				if (v > tree[loc].mn) {
					tree[loc].mn = v;
					lazy[loc] = max(lazy[loc], v);
				}
				return;
			}
		}
		int m = s + e >> 1;
		upd(s, m, l, r, v, loc * 2);
		upd(m + 1, e, l, r, v, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	void upd(int low, int r, int v) { upd(1, N, low, r, v); }
	inline node query(int s, int e, int l, int r, int loc = 1) {
		if (s != e) prop(loc);
		if (e < l || r < s) return node(-1);
		if (l <= s && e <= r) return tree[loc];
		int m = s + e >> 1;
		return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
	}
	inline node query(int l, int r) { return query(1, N, l, r); }
}
inline ll rsum(ll n) { return (n * (n + 1) / 2) % MOD; }
inline ll rsum(ll l, ll r) { return rsum(r) - rsum(l - 1); }
namespace minseg {
	int tree[MAX * 4];
	void init(int s, int e, int loc = 1) {
		if (s == e) {
			tree[loc] = H[s];
			return;
		}
		int m = s + e >> 1;
		init(s, m, loc * 2);
		init(m + 1, e, loc * 2 + 1);
		tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
	}
	inline void prop(int loc) { for (auto c : { loc * 2, loc * 2 + 1 }) tree[c] = max(tree[c], tree[loc]); }
	inline void upd(int s, int e, int l, int r, int x, int loc = 1) {
		if (s != e) prop(loc);
		if (e < l || r < s) return;
		if (l <= s && e <= r) {
			tree[loc] = max(tree[loc], x);
			return;
		}
		int m = s + e >> 1;
		upd(s, m, l, r, x, loc * 2);
		upd(m + 1, e, l, r, x, loc * 2 + 1);
		tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
	}
	inline void upd(int l, int r, int x) { upd(1, N, l, r, x); }
	inline int get(int s, int e, int i, int loc = 1) {
		if (s != e) prop(loc);
		if (e < i || i < s) return INF;
		if (s == e) return tree[loc];
		int m = s + e >> 1;
		return min(get(s, m, i, loc * 2), get(m + 1, e, i, loc * 2 + 1));
	}
	inline int get(int i) { return get(1, N, i); }
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	segtree::N = N;
	int i;
	ll ans = 0;
	int mv = 1;
	for (i = 1; i <= N; i++) cin >> H[i];
	for (i = 1; i <= N; i++) if (H[mv] < H[i]) mv = i;
	for (i = 1; i <= N; i++) ch[i] = H[i];
	for (i = 1; i <= mv; i++) ch[i] = max(ch[i], ch[i - 1]);
	for (i = N; i >= mv; i--) ch[i] = max(ch[i], ch[i + 1]);
	for (i = 1; i <= N; i++) ans += rsum(H[i], ch[i] - 1), ans %= MOD;
	segtree::init(1, N);
	minseg::init(1, N);
	int low, high;
	low = high = -1;
	for (i = 1; i < N; i++) if (H[i] > H[i + 1]) {
		low = i;
		break;
	}
	if (!~low) {
		cout << 0 << ln;
		return 0;
	}
	for (i = N; i > 1; i--) if (H[i] > H[i - 1]) {
		high = i;
		break;
	}
	if (!~high) {
		cout << 0 << ln;
		return 0;
	}
	if (low >= high) {
		cout << 0 << ln;
		return 0;
	}
	set<int> lst, rst;
	for (i = 1; i <= low; i++) lst.insert(H[i]);
	for (i = high; i <= N; i++) rst.insert(H[i]);
	int rot = 0;
	while (low < high) {
		rot++;
		assert(rot <= N * 10);
		while (low < N && minseg::get(low) <= minseg::get(low + 1)) low++, lst.insert(H[low]);
		while (high > 1 && minseg::get(high) <= minseg::get(high - 1)) high--, rst.insert(H[high]);
		if (low >= high) break;
		auto res = segtree::query(low + 1, high - 1);
		int mn = res.mn;
		int n = res.cnt;
		auto itl = lst.upper_bound(mn);
		auto itr = rst.upper_bound(mn);
		int up = min(res.mn2, min(*itl, *itr));
		int ml = min(*itl, segtree::query(low, res.mnl).mn2);
		int mr = min(*itr, segtree::query(res.mnr, high).mn2);
		if (res.cnt == 1) {
			ans += 1ll * (ml + mr) * (up - mn);
			segtree::upd(low, high, up);
			minseg::upd(low, high, up);
			ans %= MOD;
			continue;
		}
		ans += rsum(mn + 1, up) * (n * 2 - 3);
		ans %= MOD;
		ans += 1ll * (0ll + up + ml + mr) * (up - mn);
		ans %= MOD;
		segtree::upd(low, high, up);
		minseg::upd(low, high, up);
	}
	ans %= MOD;
	if (ans < 0) ans += MOD;
	cout << ans << ln;
}

Compilation message

Main.cpp: In function 'void segtree::init(int, int, int)':
Main.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In function 'void segtree::upd(int, int, int, int, int, int)':
Main.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In function 'node segtree::query(int, int, int, int, int)':
Main.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In function 'void minseg::init(int, int, int)':
Main.cpp:112:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In function 'void minseg::upd(int, int, int, int, int, int)':
Main.cpp:125:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In function 'int minseg::get(int, int, int, int)':
Main.cpp:135:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |   int m = s + e >> 1;
      |           ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct
35 Correct 46 ms 79688 KB Output is correct
36 Correct 47 ms 79704 KB Output is correct
37 Correct 45 ms 79820 KB Output is correct
38 Correct 45 ms 79760 KB Output is correct
39 Correct 46 ms 79696 KB Output is correct
40 Correct 36 ms 79468 KB Output is correct
41 Correct 35 ms 79516 KB Output is correct
42 Correct 35 ms 79572 KB Output is correct
43 Correct 43 ms 79760 KB Output is correct
44 Correct 44 ms 79788 KB Output is correct
45 Correct 45 ms 79692 KB Output is correct
46 Correct 47 ms 79748 KB Output is correct
47 Correct 47 ms 79792 KB Output is correct
48 Correct 45 ms 79672 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct
35 Correct 46 ms 79688 KB Output is correct
36 Correct 47 ms 79704 KB Output is correct
37 Correct 45 ms 79820 KB Output is correct
38 Correct 45 ms 79760 KB Output is correct
39 Correct 46 ms 79696 KB Output is correct
40 Correct 36 ms 79468 KB Output is correct
41 Correct 35 ms 79516 KB Output is correct
42 Correct 35 ms 79572 KB Output is correct
43 Correct 43 ms 79760 KB Output is correct
44 Correct 44 ms 79788 KB Output is correct
45 Correct 45 ms 79692 KB Output is correct
46 Correct 47 ms 79748 KB Output is correct
47 Correct 47 ms 79792 KB Output is correct
48 Correct 45 ms 79672 KB Output is correct
49 Correct 48 ms 79748 KB Output is correct
50 Correct 49 ms 79696 KB Output is correct
51 Correct 56 ms 79688 KB Output is correct
52 Correct 46 ms 79744 KB Output is correct
53 Correct 45 ms 79764 KB Output is correct
54 Correct 38 ms 79548 KB Output is correct
55 Correct 42 ms 79464 KB Output is correct
56 Correct 35 ms 79520 KB Output is correct
57 Correct 43 ms 79708 KB Output is correct
58 Correct 43 ms 79740 KB Output is correct
59 Correct 45 ms 79780 KB Output is correct
60 Correct 49 ms 79720 KB Output is correct
61 Correct 47 ms 79696 KB Output is correct
62 Correct 50 ms 79692 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct
35 Correct 971 ms 103652 KB Output is correct
36 Correct 963 ms 103780 KB Output is correct
37 Correct 956 ms 103568 KB Output is correct
38 Correct 964 ms 103620 KB Output is correct
39 Correct 1018 ms 103660 KB Output is correct
40 Correct 34 ms 79368 KB Output is correct
41 Correct 32 ms 79364 KB Output is correct
42 Correct 449 ms 103636 KB Output is correct
43 Correct 444 ms 103644 KB Output is correct
44 Correct 444 ms 103648 KB Output is correct
45 Correct 565 ms 103648 KB Output is correct
46 Correct 577 ms 103808 KB Output is correct
47 Correct 554 ms 103648 KB Output is correct
48 Correct 690 ms 103644 KB Output is correct
49 Correct 683 ms 103640 KB Output is correct
50 Correct 649 ms 103672 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct
35 Correct 46 ms 79688 KB Output is correct
36 Correct 47 ms 79704 KB Output is correct
37 Correct 45 ms 79820 KB Output is correct
38 Correct 45 ms 79760 KB Output is correct
39 Correct 46 ms 79696 KB Output is correct
40 Correct 36 ms 79468 KB Output is correct
41 Correct 35 ms 79516 KB Output is correct
42 Correct 35 ms 79572 KB Output is correct
43 Correct 43 ms 79760 KB Output is correct
44 Correct 44 ms 79788 KB Output is correct
45 Correct 45 ms 79692 KB Output is correct
46 Correct 47 ms 79748 KB Output is correct
47 Correct 47 ms 79792 KB Output is correct
48 Correct 45 ms 79672 KB Output is correct
49 Correct 971 ms 103652 KB Output is correct
50 Correct 963 ms 103780 KB Output is correct
51 Correct 956 ms 103568 KB Output is correct
52 Correct 964 ms 103620 KB Output is correct
53 Correct 1018 ms 103660 KB Output is correct
54 Correct 34 ms 79368 KB Output is correct
55 Correct 32 ms 79364 KB Output is correct
56 Correct 449 ms 103636 KB Output is correct
57 Correct 444 ms 103644 KB Output is correct
58 Correct 444 ms 103648 KB Output is correct
59 Correct 565 ms 103648 KB Output is correct
60 Correct 577 ms 103808 KB Output is correct
61 Correct 554 ms 103648 KB Output is correct
62 Correct 690 ms 103644 KB Output is correct
63 Correct 683 ms 103640 KB Output is correct
64 Correct 649 ms 103672 KB Output is correct
65 Correct 3258 ms 142820 KB Output is correct
66 Correct 3823 ms 157344 KB Output is correct
67 Correct 3974 ms 158644 KB Output is correct
68 Correct 3722 ms 145900 KB Output is correct
69 Correct 3562 ms 138208 KB Output is correct
70 Correct 442 ms 103632 KB Output is correct
71 Correct 453 ms 103700 KB Output is correct
72 Correct 447 ms 103636 KB Output is correct
73 Correct 2317 ms 133372 KB Output is correct
74 Correct 2633 ms 163080 KB Output is correct
75 Correct 3148 ms 162960 KB Output is correct
76 Correct 3102 ms 140656 KB Output is correct
77 Correct 2869 ms 146200 KB Output is correct
78 Correct 3066 ms 140504 KB Output is correct

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79372 KB Output is correct
2 Correct 32 ms 79372 KB Output is correct
3 Correct 31 ms 79372 KB Output is correct
4 Correct 34 ms 79512 KB Output is correct
5 Correct 32 ms 79460 KB Output is correct
6 Correct 33 ms 79540 KB Output is correct
7 Correct 33 ms 79564 KB Output is correct
8 Correct 34 ms 79564 KB Output is correct
9 Correct 33 ms 79468 KB Output is correct
10 Correct 34 ms 79540 KB Output is correct
11 Correct 35 ms 79488 KB Output is correct
12 Correct 35 ms 79568 KB Output is correct
13 Correct 37 ms 79504 KB Output is correct
14 Correct 33 ms 79396 KB Output is correct
15 Correct 34 ms 79372 KB Output is correct
16 Correct 35 ms 79452 KB Output is correct
17 Correct 37 ms 79520 KB Output is correct
18 Correct 43 ms 79532 KB Output is correct
19 Correct 36 ms 79568 KB Output is correct
20 Correct 38 ms 79536 KB Output is correct
21 Correct 40 ms 79572 KB Output is correct
22 Correct 54 ms 79484 KB Output is correct
23 Correct 35 ms 79564 KB Output is correct
24 Correct 37 ms 79584 KB Output is correct
25 Correct 36 ms 79540 KB Output is correct
26 Correct 36 ms 79572 KB Output is correct
27 Correct 36 ms 79472 KB Output is correct
28 Correct 35 ms 79564 KB Output is correct
29 Correct 36 ms 79472 KB Output is correct
30 Correct 35 ms 79308 KB Output is correct
31 Correct 34 ms 79332 KB Output is correct
32 Correct 38 ms 79340 KB Output is correct
33 Correct 34 ms 79404 KB Output is correct
34 Correct 34 ms 79316 KB Output is correct
35 Correct 46 ms 79688 KB Output is correct
36 Correct 47 ms 79704 KB Output is correct
37 Correct 45 ms 79820 KB Output is correct
38 Correct 45 ms 79760 KB Output is correct
39 Correct 46 ms 79696 KB Output is correct
40 Correct 36 ms 79468 KB Output is correct
41 Correct 35 ms 79516 KB Output is correct
42 Correct 35 ms 79572 KB Output is correct
43 Correct 43 ms 79760 KB Output is correct
44 Correct 44 ms 79788 KB Output is correct
45 Correct 45 ms 79692 KB Output is correct
46 Correct 47 ms 79748 KB Output is correct
47 Correct 47 ms 79792 KB Output is correct
48 Correct 45 ms 79672 KB Output is correct
49 Correct 48 ms 79748 KB Output is correct
50 Correct 49 ms 79696 KB Output is correct
51 Correct 56 ms 79688 KB Output is correct
52 Correct 46 ms 79744 KB Output is correct
53 Correct 45 ms 79764 KB Output is correct
54 Correct 38 ms 79548 KB Output is correct
55 Correct 42 ms 79464 KB Output is correct
56 Correct 35 ms 79520 KB Output is correct
57 Correct 43 ms 79708 KB Output is correct
58 Correct 43 ms 79740 KB Output is correct
59 Correct 45 ms 79780 KB Output is correct
60 Correct 49 ms 79720 KB Output is correct
61 Correct 47 ms 79696 KB Output is correct
62 Correct 50 ms 79692 KB Output is correct
63 Correct 971 ms 103652 KB Output is correct
64 Correct 963 ms 103780 KB Output is correct
65 Correct 956 ms 103568 KB Output is correct
66 Correct 964 ms 103620 KB Output is correct
67 Correct 1018 ms 103660 KB Output is correct
68 Correct 34 ms 79368 KB Output is correct
69 Correct 32 ms 79364 KB Output is correct
70 Correct 449 ms 103636 KB Output is correct
71 Correct 444 ms 103644 KB Output is correct
72 Correct 444 ms 103648 KB Output is correct
73 Correct 565 ms 103648 KB Output is correct
74 Correct 577 ms 103808 KB Output is correct
75 Correct 554 ms 103648 KB Output is correct
76 Correct 690 ms 103644 KB Output is correct
77 Correct 683 ms 103640 KB Output is correct
78 Correct 649 ms 103672 KB Output is correct
79 Correct 3258 ms 142820 KB Output is correct
80 Correct 3823 ms 157344 KB Output is correct
81 Correct 3974 ms 158644 KB Output is correct
82 Correct 3722 ms 145900 KB Output is correct
83 Correct 3562 ms 138208 KB Output is correct
84 Correct 442 ms 103632 KB Output is correct
85 Correct 453 ms 103700 KB Output is correct
86 Correct 447 ms 103636 KB Output is correct
87 Correct 2317 ms 133372 KB Output is correct
88 Correct 2633 ms 163080 KB Output is correct
89 Correct 3148 ms 162960 KB Output is correct
90 Correct 3102 ms 140656 KB Output is correct
91 Correct 2869 ms 146200 KB Output is correct
92 Correct 3066 ms 140504 KB Output is correct
93 Correct 443 ms 103648 KB Output is correct
94 Correct 3160 ms 150504 KB Output is correct
95 Correct 3267 ms 150488 KB Output is correct
96 Correct 3324 ms 150532 KB Output is correct
97 Correct 4472 ms 150628 KB Output is correct
98 Correct 4447 ms 150544 KB Output is correct
99 Correct 4103 ms 150640 KB Output is correct
100 Execution timed out 5030 ms 150820 KB Time limit exceeded
101 Halted 0 ms 0 KB -