oj.uz

Submission #654315

# Submission time Handle Problem Language Result Execution time Memory
654315 2022-10-31T00:20:39 Z resting Radio Towers (IOI22_towers) C++17
100 / 100
 3023 ms 538668 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define mx 100005

struct tree {
	struct node {
		node(int l, int r) : l(l), r(r) {}
		int l = 0; int r = 0; int v = 0;
		node* lc = nullptr;
		node* rc = nullptr;
	};
	vector<node*> rt;
	vector<int> nums;

	tree() {
		nums.push_back(numeric_limits<int>::min());
		rt.push_back(build(0, mx));
	}
	void upd(int idx, int val, int v) {
		//cout << "index: " << idx << "," << "value: " << val << "," << "time: " << v << endl;
		nums.push_back(v); // v = time
		rt.push_back(upd2(rt.back(), idx, val));
	}

	node* build(int l, int r) {
		node* rt = new node(l, r);
		if (l == r) return rt;
		int m = (l + r) / 2;
		rt->lc = build(l, m);
		rt->rc = build(m + 1, r);
		return rt;
	}

	node* upd2(node* rt, int idx, int v) {
		//return the root
		if (rt->l > idx || rt->r < idx) return rt;
		node* tr = new node(*rt); //copy?
		if (tr->l == tr->r) {
			tr->v = v;
			return tr;
		}
		tr->lc = upd2(tr->lc, idx, v);
		tr->rc = upd2(tr->rc, idx, v);
		tr->v = tr->lc->v + tr->rc->v;
		return tr;
	}
	
	array<int, 3> query(int l, int r, int t) {
		node* vv = rt.at((upper_bound(nums.begin(), nums.end(), t) - nums.begin())-1);
		return { queryL(vv, l), queryR(vv, r), queryS(vv, l, r)};
	}

	int queryS(node* rt, int l, int r) {
		if (rt->l > r || rt->r < l)return 0;
		if (rt->l >= l && rt->r <= r) return rt->v;
		return queryS(rt->lc, l, r) + queryS(rt->rc, l, r);
	}

	int queryL(node* rt, int l) { //query left most with index >= l and value >= v
		if (rt->r < l) return -1;
		if (!rt->v) return -1;
		if (rt->l == rt->r) return rt->l;
		int res = queryL(rt->lc, l);
		return res == -1 ? queryL(rt->rc, l) : res;
	}

	int queryR(node* rt, int r) { //query right most with index <= r
		if (rt->l > r) return -1;
		if (!rt->v) return -1;
		if (rt->l == rt->r) return rt->l;
		int res = queryR(rt->rc, r);
		return res == -1 ? queryR(rt->lc, r) : res;
	}

} open, close;

vector<int> h;

//struct mintree { //ehh should be sparse tablebut wtv
//	struct node {
//		node(int l, int r) : l(l), r(r) {};
//		int v = numeric_limits<int>::max();
//		int l, r;
//		node *lc = 0, *rc = 0;
//	};
//	node* rt;
//	mintree() {
//		rt = build(0, mx);
//	}
//	node* build(int l, int r) {
//		node* rt = new node(l, r);
//		if (l == r) return rt;
//		int m = (l + r) / 2;
//		rt->lc = build(l, m);
//		rt->rc = build(m + 1, r);
//		return rt;
//	}
//	void upd(int i, int v) {
//		upd2(rt, i, v);
//	}
//	void upd2(node* rt, int i, int v) {
//		if (i < rt->l || i > rt->r) return;
//		if (rt->l == rt->r) {
//			rt->v = v;
//			return;
//		}
//		upd2(rt->lc, i, v); upd2(rt->rc, i, v);
//		rt->v = min(rt->lc->v, rt->rc->v);
//	}
//	int query(int l, int r) {
//		return query2(rt, l, r);
//	}
//	int query2(node* rt, int l, int r) {
//		if (l > rt->r || r < rt->l) return numeric_limits<int>::max();
//		if (rt->l >= l && rt->r <= r) return rt->v;
//		return min(query2(rt->lc, l, r), query2(rt->rc, l, r));
//	}
//} ac2;

#define ll int
struct difftree { //what the fk am i doing
	struct node {
		node(int l, int r) : l(l), r(r) {};
		ll mn = std::numeric_limits<int>::max()/2;
		ll ma = std::numeric_limits<int>::min()/2;
		ll incdif = 0, decdif = 0;
		int l, r;
		node* lc = 0, * rc = 0;
	};
	node* rt = 0;
	difftree() {
		rt = build(0, mx);
		//cout << rt->l << "," << rt->r << endl;
	}
	node* build(int l, int r) {
		node* rt = new node(l, r);
		if (l == r) return rt;
		int m = (l + r) / 2;
		rt->lc = build(l, m);
		rt->rc = build(m + 1, r);
		return rt;
	}
	void upd(int i, int v) {
		upd2(rt, i, v);
	}
	void upd2(node* rt, int i, int v) {
		if (i < rt->l || i > rt->r) return;
		if (rt->l == rt->r) {
			rt->mn = rt->ma = v;
			return;
		}
		upd2(rt->lc, i, v); upd2(rt->rc, i, v);
		rt->mn = min(rt->lc->mn, rt->rc->mn);
		rt->ma = max(rt->lc->ma, rt->rc->ma);
		rt->incdif = max(max(rt->lc->incdif, rt->rc->incdif), rt->rc->ma - rt->lc->mn);
		rt->decdif = max(max(rt->lc->decdif, rt->rc->decdif), rt->lc->ma - rt->rc->mn);
	}
	int incdif(int l, int r) {
		node amogus = query2(rt, l, r);
		int tmp = amogus.incdif;
		return tmp;
	}
	int decdif(int l, int r) {
		node amogus = query2(rt, l, r);
		int tmp = amogus.decdif;
		return tmp;
	}
	node query2(node* rt, int l, int r) {
		//cout << "gonna kms" << endl;
		//cout << l << "," << rt->l << "," << r << "," << rt->r << endl;
		if (l > rt->r || r < rt->l) return node(-1,-1);
		if (rt->l >= l && rt->r <= r) return *rt;
		node owo(-1, -1);
		node lc = query2(rt->lc, l, r);
		node rc = query2(rt->rc, l, r);
		owo.mn = min(lc.mn, rc.mn);
		owo.ma = max(lc.ma, rc.ma);
		owo.incdif = max(max(lc.incdif, rc.incdif), rc.ma - lc.mn);
		owo.decdif = max(max(lc.decdif, rc.decdif), lc.ma - rc.mn);
		return owo;
	}
	int walk(int l, int D) {
		node tmp = walking(rt, node(-1, -1), l, D);
		return tmp.r;
	}
	node merge(node lc, node rc) {
		node owo(-1, -1);
		owo.mn = min(lc.mn, rc.mn);
		owo.ma = max(lc.ma, rc.ma);
		owo.incdif = max(max(lc.incdif, rc.incdif), rc.ma - lc.mn);
		owo.decdif = max(max(lc.decdif, rc.decdif), lc.ma - rc.mn);
		owo.r = rc.r;
		return owo;
	}
	node walking(node* rt, node left, int l, int D) {
		if (l > rt->r) return node(-1, -1);
		if (rt->l >= l) {
			node tmp = merge(left, *rt);
			if (tmp.incdif < D) return tmp;
		}
		if (rt->l == rt->r) {
			return merge(left, *rt);
		}

		node lc = walking(rt->lc, left, l, D);
		if (lc.incdif >= D) return lc;
		node owo = walking(rt->rc, lc, l, D);
		return owo;
	}
} diff;
//
//struct dsu {
//	vector<int> p, r;
//	dsu() {
//		p.resize(mx, -1);
//		r.resize(mx, 0);
//	}
//	int par(int x) {
//		return p.at(x) == -1 ? x : p.at(x) = par(p.at(x));
//	}
//	void merge(int a, int b) {
//		a = par(a), b = par(b); 
//		if (a == b) return;
//		//attaching b to a, so r.at(a) must be bigger
//		if (r.at(a) < r.at(b)) swap(a, b);
//		if (r.at(a) == r.at(b)) r.at(a)++;
//		p.at(b) = a;
//	}
//};


void init(int N, vector<int> H) {
	h = H;
	h.insert(h.begin(), numeric_limits<int>::max()); N++;
	set<int> ranges;
	for (int i = 0; i < N; i++)
		ranges.insert(i);
	vector<int> mn = h;
	vector<bool> exists(N, 1);
	set<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		//ac2.upd(i, h.at(i));
		diff.upd(i, h.at(i));
		open.upd(i, 1, numeric_limits<int>::min());
		close.upd(i+1, 1, numeric_limits<int>::min());
		int v = numeric_limits<int>::max();
		if (i) v = min(v, h.at(i) - mn.at(i));
		if (i < N - 1)v = min(v, h.at(i + 1) - mn.at(i));
		q.insert({ v, i });
	}
	int time = numeric_limits<int>::min();
	while (q.size()) {
		auto [a, b] = *q.begin();
		time = max(time, a);
		q.erase(q.begin());
		if (!exists.at(b)) continue;

		auto x = ranges.find(b);
		if (b && h.at(b) - mn.at(b) <= a) {
			//deletus
			auto x2 = x; x2--;
			if (exists.at(*x2)) {
				exists.at(*x) = 0;
				open.upd(*x, 0, time);
				auto x3 = x; x3++;
				if (x3 == ranges.end()) close.upd(N, 0, time);
				else close.upd(*x3, 0, time);
				continue;
			}
			int tmp = mn.at(b);
			exists.at(*x) = 0; 
			exists.at(*x2) = 1;
			open.upd(*x, 0, time);
			open.upd(*x2, 1, time);
			ranges.erase(x--);
			mn.at(*x) = min(mn.at(*x), tmp);
		}
		else {
			auto x2 = x; x2++;
			//assert(x2 != ranges.end()); //troll
			if (x2 == ranges.end()) {
				continue;
			}
			if (exists.at(*x2)) {
				open.upd(*x, 0, time);
				close.upd(*x2, 0, time);
				exists.at(*x) = 0;
				continue;
			}
			if (x2 != ranges.end() && h.at(*x2) - mn.at(*x) <= a) {
				mn.at(*x) = min(mn.at(*x), mn.at(*x2));
				exists.at(*x2) = 0; 
				close.upd(*x2, 0, time);

				auto x3 = x2; x3++;
				if(x3 != ranges.end())close.upd(*x3, 1, time);
				else close.upd(N, 1, time);
				ranges.erase(x2);
			}
			else {
				break;
			}
		}
		//x is result

		b = *x; int v = numeric_limits<int>::max();
		if (b) v = min(v, h.at(b) - mn.at(b));
		x++;
		if (x != ranges.end()) v = min(v, h.at(*x) - mn.at(b));
		q.insert({ v, b });

		//yeahhhhhhh......
	}
	h = H;
}

int max_towers(int L, int R, int D) {
	L++, R++; D--;
	//this is so sus
	auto [a, b, c] = open.query(L, R, D);
	auto [e, f, g] = close.query(L, R, D);


	//auto .at(x, y, z) = open.query(0, 7, numeric_limits<int>::min());
	//cout << x << "," << y << "," << z << endl;
	//cout << c << "," << g << endl;

	if (c && g && e <= a) {
		g--;
	}
	if (c && g && b >= f) {
		c--;
	}


	int bruh = 1;
	int vvvv = diff.walk(L, D + 1);
	if (vvvv < R && diff.decdif(vvvv, R) >= D + 1) {
		bruh = 2;
	}
	if (c == 0 || g == 0) {
		return bruh;
	}
	//if (c == 0 || g == 0) {
	//	//AMONGUS
	//	int l = L, r = R, m = 0;
	//	int inc = 0, dec = 0;
	//	while (l < r) {
	//		m = (l + r) / 2;
	//		 inc = diff.incdif(L, m);
	//		 dec = diff.decdif(m, R);
	//		//cout <<L<<","<<R<<","<<m << "," << inc << "," << dec << endl;
	//		if (min(inc, dec) >= D+1) break;
	//		if (max(inc, dec) < D + 1)break;
 //			if (inc < dec)
	//			l = m + 1;
	//		else 
	//			r = m - 1;
	//	}
	//	//cout << "." << endl;
	//	if (min(inc, dec) >= D+1) {
	//		return 2;
	//	}
	//	else {
	//		return 1;
	//	}
	//}
	//cout << a << "," << b << "," << c << endl;
	//cout << e << "," << f << "," << g << endl;
	//assert(a != -1);
	//assert(b != -1);
	//assert(e != -1);
	//assert(f != -1);

	
	//assert(c == g);
	//cout << diff.incdif(L, a) << "," << L << "," << a << endl;
	if (diff.incdif(L, a) >= D+1) c++;
	if (diff.decdif(f, R) >= D+1) c++;
	return max(c, bruh);
}

////
//int main() {
//	int N, Q;
//	assert(2 == scanf("%d %d", &N, &Q));
//	std::vector<int> H(N);
//	for (int i = 0; i < N; ++i) {
//		assert(1 == scanf("%d", &H.at(i)));
//	}
//	init(N, H);
//
//	for (int i = 0; i < Q; ++i) {
//		int L, R, D;
//		assert(3 == scanf("%d %d %d", &L, &R, &D));
//		printf("%d\n", max_towers(L, R, D));
//	}
//	return 0;
//}

Compilation message

towers.cpp:123: warning: "ll" redefined
  123 | #define ll int
      | 
towers.cpp:4: note: this is the location of the previous definition
    4 | #define ll long long
      |

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 332388 KB Output is correct
2 Correct 2330 ms 538340 KB Output is correct
3 Correct 2053 ms 538424 KB Output is correct
4 Correct 2071 ms 538452 KB Output is correct
5 Correct 2309 ms 535684 KB Output is correct
6 Correct 1989 ms 538440 KB Output is correct
7 Correct 2266 ms 535624 KB Output is correct
8 Correct 24 ms 28360 KB Output is correct
9 Correct 37 ms 38584 KB Output is correct
10 Correct 41 ms 38576 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30644 KB Output is correct
2 Correct 39 ms 38600 KB Output is correct
3 Correct 37 ms 38600 KB Output is correct
4 Correct 38 ms 38604 KB Output is correct
5 Correct 38 ms 38516 KB Output is correct
6 Correct 37 ms 38532 KB Output is correct
7 Correct 39 ms 38636 KB Output is correct
8 Correct 36 ms 38596 KB Output is correct
9 Correct 39 ms 38496 KB Output is correct
10 Correct 38 ms 38472 KB Output is correct
11 Correct 37 ms 38600 KB Output is correct
12 Correct 24 ms 28496 KB Output is correct
13 Correct 37 ms 38596 KB Output is correct
14 Correct 39 ms 38600 KB Output is correct
15 Correct 46 ms 38600 KB Output is correct
16 Correct 41 ms 38600 KB Output is correct
17 Correct 38 ms 38512 KB Output is correct
18 Correct 37 ms 38600 KB Output is correct
19 Correct 39 ms 38632 KB Output is correct
20 Correct 38 ms 38592 KB Output is correct
21 Correct 38 ms 38600 KB Output is correct
22 Correct 38 ms 38520 KB Output is correct
23 Correct 37 ms 38612 KB Output is correct
24 Correct 36 ms 38504 KB Output is correct
25 Correct 30 ms 32988 KB Output is correct
26 Correct 37 ms 38600 KB Output is correct
27 Correct 37 ms 38600 KB Output is correct
28 Correct 38 ms 38600 KB Output is correct
29 Correct 45 ms 38552 KB Output is correct
30 Correct 39 ms 38588 KB Output is correct
31 Correct 43 ms 38588 KB Output is correct
32 Correct 38 ms 38600 KB Output is correct
33 Correct 37 ms 38600 KB Output is correct
34 Correct 36 ms 38520 KB Output is correct
35 Correct 38 ms 38660 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30644 KB Output is correct
2 Correct 39 ms 38600 KB Output is correct
3 Correct 37 ms 38600 KB Output is correct
4 Correct 38 ms 38604 KB Output is correct
5 Correct 38 ms 38516 KB Output is correct
6 Correct 37 ms 38532 KB Output is correct
7 Correct 39 ms 38636 KB Output is correct
8 Correct 36 ms 38596 KB Output is correct
9 Correct 39 ms 38496 KB Output is correct
10 Correct 38 ms 38472 KB Output is correct
11 Correct 37 ms 38600 KB Output is correct
12 Correct 24 ms 28496 KB Output is correct
13 Correct 37 ms 38596 KB Output is correct
14 Correct 39 ms 38600 KB Output is correct
15 Correct 46 ms 38600 KB Output is correct
16 Correct 41 ms 38600 KB Output is correct
17 Correct 38 ms 38512 KB Output is correct
18 Correct 37 ms 38600 KB Output is correct
19 Correct 39 ms 38632 KB Output is correct
20 Correct 38 ms 38592 KB Output is correct
21 Correct 38 ms 38600 KB Output is correct
22 Correct 38 ms 38520 KB Output is correct
23 Correct 37 ms 38612 KB Output is correct
24 Correct 36 ms 38504 KB Output is correct
25 Correct 30 ms 32988 KB Output is correct
26 Correct 37 ms 38600 KB Output is correct
27 Correct 37 ms 38600 KB Output is correct
28 Correct 38 ms 38600 KB Output is correct
29 Correct 45 ms 38552 KB Output is correct
30 Correct 39 ms 38588 KB Output is correct
31 Correct 43 ms 38588 KB Output is correct
32 Correct 38 ms 38600 KB Output is correct
33 Correct 37 ms 38600 KB Output is correct
34 Correct 36 ms 38520 KB Output is correct
35 Correct 38 ms 38660 KB Output is correct
36 Correct 618 ms 358400 KB Output is correct
37 Correct 948 ms 535624 KB Output is correct
38 Correct 1056 ms 535564 KB Output is correct
39 Correct 1044 ms 535604 KB Output is correct
40 Correct 1048 ms 535560 KB Output is correct
41 Correct 1002 ms 535464 KB Output is correct
42 Correct 1002 ms 535544 KB Output is correct
43 Correct 636 ms 538444 KB Output is correct
44 Correct 1040 ms 535616 KB Output is correct
45 Correct 634 ms 531876 KB Output is correct
46 Correct 929 ms 535588 KB Output is correct
47 Correct 958 ms 535576 KB Output is correct
48 Correct 995 ms 535524 KB Output is correct
49 Correct 1016 ms 535512 KB Output is correct
50 Correct 1034 ms 535632 KB Output is correct
51 Correct 675 ms 538512 KB Output is correct
52 Correct 1030 ms 535568 KB Output is correct
53 Correct 1020 ms 535544 KB Output is correct
54 Correct 1008 ms 535564 KB Output is correct
55 Correct 966 ms 535640 KB Output is correct
56 Correct 618 ms 534636 KB Output is correct
57 Correct 956 ms 518372 KB Output is correct
58 Correct 1014 ms 535708 KB Output is correct
59 Correct 1030 ms 535512 KB Output is correct
60 Correct 998 ms 535716 KB Output is correct
61 Correct 984 ms 535504 KB Output is correct
62 Correct 963 ms 535620 KB Output is correct
63 Correct 1008 ms 535504 KB Output is correct
64 Correct 614 ms 538512 KB Output is correct
65 Correct 955 ms 535496 KB Output is correct
66 Correct 624 ms 536416 KB Output is correct
67 Correct 923 ms 535716 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2354 ms 532064 KB Output is correct
2 Correct 2558 ms 535684 KB Output is correct
3 Correct 2629 ms 535612 KB Output is correct
4 Correct 2629 ms 535584 KB Output is correct
5 Correct 2520 ms 535656 KB Output is correct
6 Correct 2594 ms 535604 KB Output is correct
7 Correct 2490 ms 535744 KB Output is correct
8 Correct 2081 ms 538624 KB Output is correct
9 Correct 2289 ms 535596 KB Output is correct
10 Correct 2125 ms 535504 KB Output is correct
11 Correct 2486 ms 535496 KB Output is correct
12 Correct 2260 ms 538500 KB Output is correct
13 Correct 2256 ms 535568 KB Output is correct
14 Correct 24 ms 28444 KB Output is correct
15 Correct 42 ms 38596 KB Output is correct
16 Correct 39 ms 38616 KB Output is correct
17 Correct 944 ms 535628 KB Output is correct
18 Correct 992 ms 535548 KB Output is correct
19 Correct 1026 ms 535664 KB Output is correct
20 Correct 935 ms 535592 KB Output is correct
21 Correct 630 ms 538576 KB Output is correct
22 Correct 967 ms 535580 KB Output is correct
23 Correct 1002 ms 535488 KB Output is correct
24 Correct 998 ms 535760 KB Output is correct
25 Correct 899 ms 535660 KB Output is correct
26 Correct 646 ms 534780 KB Output is correct
27 Correct 38 ms 38552 KB Output is correct
28 Correct 37 ms 38528 KB Output is correct
29 Correct 38 ms 38560 KB Output is correct
30 Correct 37 ms 38524 KB Output is correct
31 Correct 37 ms 38600 KB Output is correct
32 Correct 40 ms 38600 KB Output is correct
33 Correct 39 ms 38512 KB Output is correct
34 Correct 40 ms 38620 KB Output is correct
35 Correct 37 ms 38600 KB Output is correct
36 Correct 37 ms 38600 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 150048 KB Output is correct
2 Correct 2295 ms 535520 KB Output is correct
3 Correct 2327 ms 535616 KB Output is correct
4 Correct 2336 ms 535624 KB Output is correct
5 Correct 2390 ms 535672 KB Output is correct
6 Correct 2398 ms 535600 KB Output is correct
7 Correct 2160 ms 535548 KB Output is correct
8 Correct 1691 ms 538416 KB Output is correct
9 Correct 1797 ms 535636 KB Output is correct
10 Correct 1716 ms 538492 KB Output is correct
11 Correct 2143 ms 535644 KB Output is correct
12 Correct 938 ms 535568 KB Output is correct
13 Correct 1002 ms 535708 KB Output is correct
14 Correct 1027 ms 535696 KB Output is correct
15 Correct 925 ms 535512 KB Output is correct
16 Correct 706 ms 534576 KB Output is correct
17 Correct 960 ms 518388 KB Output is correct
18 Correct 1051 ms 535628 KB Output is correct
19 Correct 1094 ms 535788 KB Output is correct
20 Correct 1065 ms 535584 KB Output is correct
21 Correct 1078 ms 535552 KB Output is correct
22 Correct 1012 ms 535600 KB Output is correct
23 Correct 1022 ms 535592 KB Output is correct
24 Correct 613 ms 538432 KB Output is correct
25 Correct 910 ms 535644 KB Output is correct
26 Correct 628 ms 536380 KB Output is correct
27 Correct 969 ms 535612 KB Output is correct
28 Correct 39 ms 38592 KB Output is correct
29 Correct 39 ms 38600 KB Output is correct
30 Correct 41 ms 38568 KB Output is correct
31 Correct 38 ms 38492 KB Output is correct
32 Correct 37 ms 38600 KB Output is correct
33 Correct 31 ms 33012 KB Output is correct
34 Correct 43 ms 38572 KB Output is correct
35 Correct 39 ms 38508 KB Output is correct
36 Correct 38 ms 38524 KB Output is correct
37 Correct 39 ms 38600 KB Output is correct
38 Correct 38 ms 38512 KB Output is correct
39 Correct 38 ms 38500 KB Output is correct
40 Correct 37 ms 38600 KB Output is correct
41 Correct 38 ms 38596 KB Output is correct
42 Correct 38 ms 38536 KB Output is correct
43 Correct 38 ms 38524 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30644 KB Output is correct
2 Correct 39 ms 38600 KB Output is correct
3 Correct 37 ms 38600 KB Output is correct
4 Correct 38 ms 38604 KB Output is correct
5 Correct 38 ms 38516 KB Output is correct
6 Correct 37 ms 38532 KB Output is correct
7 Correct 39 ms 38636 KB Output is correct
8 Correct 36 ms 38596 KB Output is correct
9 Correct 39 ms 38496 KB Output is correct
10 Correct 38 ms 38472 KB Output is correct
11 Correct 37 ms 38600 KB Output is correct
12 Correct 24 ms 28496 KB Output is correct
13 Correct 37 ms 38596 KB Output is correct
14 Correct 39 ms 38600 KB Output is correct
15 Correct 46 ms 38600 KB Output is correct
16 Correct 41 ms 38600 KB Output is correct
17 Correct 38 ms 38512 KB Output is correct
18 Correct 37 ms 38600 KB Output is correct
19 Correct 39 ms 38632 KB Output is correct
20 Correct 38 ms 38592 KB Output is correct
21 Correct 38 ms 38600 KB Output is correct
22 Correct 38 ms 38520 KB Output is correct
23 Correct 37 ms 38612 KB Output is correct
24 Correct 36 ms 38504 KB Output is correct
25 Correct 30 ms 32988 KB Output is correct
26 Correct 37 ms 38600 KB Output is correct
27 Correct 37 ms 38600 KB Output is correct
28 Correct 38 ms 38600 KB Output is correct
29 Correct 45 ms 38552 KB Output is correct
30 Correct 39 ms 38588 KB Output is correct
31 Correct 43 ms 38588 KB Output is correct
32 Correct 38 ms 38600 KB Output is correct
33 Correct 37 ms 38600 KB Output is correct
34 Correct 36 ms 38520 KB Output is correct
35 Correct 38 ms 38660 KB Output is correct
36 Correct 618 ms 358400 KB Output is correct
37 Correct 948 ms 535624 KB Output is correct
38 Correct 1056 ms 535564 KB Output is correct
39 Correct 1044 ms 535604 KB Output is correct
40 Correct 1048 ms 535560 KB Output is correct
41 Correct 1002 ms 535464 KB Output is correct
42 Correct 1002 ms 535544 KB Output is correct
43 Correct 636 ms 538444 KB Output is correct
44 Correct 1040 ms 535616 KB Output is correct
45 Correct 634 ms 531876 KB Output is correct
46 Correct 929 ms 535588 KB Output is correct
47 Correct 958 ms 535576 KB Output is correct
48 Correct 995 ms 535524 KB Output is correct
49 Correct 1016 ms 535512 KB Output is correct
50 Correct 1034 ms 535632 KB Output is correct
51 Correct 675 ms 538512 KB Output is correct
52 Correct 1030 ms 535568 KB Output is correct
53 Correct 1020 ms 535544 KB Output is correct
54 Correct 1008 ms 535564 KB Output is correct
55 Correct 966 ms 535640 KB Output is correct
56 Correct 618 ms 534636 KB Output is correct
57 Correct 956 ms 518372 KB Output is correct
58 Correct 1014 ms 535708 KB Output is correct
59 Correct 1030 ms 535512 KB Output is correct
60 Correct 998 ms 535716 KB Output is correct
61 Correct 984 ms 535504 KB Output is correct
62 Correct 963 ms 535620 KB Output is correct
63 Correct 1008 ms 535504 KB Output is correct
64 Correct 614 ms 538512 KB Output is correct
65 Correct 955 ms 535496 KB Output is correct
66 Correct 624 ms 536416 KB Output is correct
67 Correct 923 ms 535716 KB Output is correct
68 Correct 2354 ms 532064 KB Output is correct
69 Correct 2558 ms 535684 KB Output is correct
70 Correct 2629 ms 535612 KB Output is correct
71 Correct 2629 ms 535584 KB Output is correct
72 Correct 2520 ms 535656 KB Output is correct
73 Correct 2594 ms 535604 KB Output is correct
74 Correct 2490 ms 535744 KB Output is correct
75 Correct 2081 ms 538624 KB Output is correct
76 Correct 2289 ms 535596 KB Output is correct
77 Correct 2125 ms 535504 KB Output is correct
78 Correct 2486 ms 535496 KB Output is correct
79 Correct 2260 ms 538500 KB Output is correct
80 Correct 2256 ms 535568 KB Output is correct
81 Correct 24 ms 28444 KB Output is correct
82 Correct 42 ms 38596 KB Output is correct
83 Correct 39 ms 38616 KB Output is correct
84 Correct 944 ms 535628 KB Output is correct
85 Correct 992 ms 535548 KB Output is correct
86 Correct 1026 ms 535664 KB Output is correct
87 Correct 935 ms 535592 KB Output is correct
88 Correct 630 ms 538576 KB Output is correct
89 Correct 967 ms 535580 KB Output is correct
90 Correct 1002 ms 535488 KB Output is correct
91 Correct 998 ms 535760 KB Output is correct
92 Correct 899 ms 535660 KB Output is correct
93 Correct 646 ms 534780 KB Output is correct
94 Correct 38 ms 38552 KB Output is correct
95 Correct 37 ms 38528 KB Output is correct
96 Correct 38 ms 38560 KB Output is correct
97 Correct 37 ms 38524 KB Output is correct
98 Correct 37 ms 38600 KB Output is correct
99 Correct 40 ms 38600 KB Output is correct
100 Correct 39 ms 38512 KB Output is correct
101 Correct 40 ms 38620 KB Output is correct
102 Correct 37 ms 38600 KB Output is correct
103 Correct 37 ms 38600 KB Output is correct
104 Correct 2214 ms 478808 KB Output is correct
105 Correct 2397 ms 535740 KB Output is correct
106 Correct 2648 ms 535744 KB Output is correct
107 Correct 2483 ms 535552 KB Output is correct
108 Correct 2706 ms 535756 KB Output is correct
109 Correct 2721 ms 535588 KB Output is correct
110 Correct 2581 ms 535564 KB Output is correct
111 Correct 2110 ms 538440 KB Output is correct
112 Correct 2130 ms 535756 KB Output is correct
113 Correct 2056 ms 538636 KB Output is correct
114 Correct 2325 ms 535608 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 332388 KB Output is correct
2 Correct 2330 ms 538340 KB Output is correct
3 Correct 2053 ms 538424 KB Output is correct
4 Correct 2071 ms 538452 KB Output is correct
5 Correct 2309 ms 535684 KB Output is correct
6 Correct 1989 ms 538440 KB Output is correct
7 Correct 2266 ms 535624 KB Output is correct
8 Correct 24 ms 28360 KB Output is correct
9 Correct 37 ms 38584 KB Output is correct
10 Correct 41 ms 38576 KB Output is correct
11 Correct 27 ms 30644 KB Output is correct
12 Correct 39 ms 38600 KB Output is correct
13 Correct 37 ms 38600 KB Output is correct
14 Correct 38 ms 38604 KB Output is correct
15 Correct 38 ms 38516 KB Output is correct
16 Correct 37 ms 38532 KB Output is correct
17 Correct 39 ms 38636 KB Output is correct
18 Correct 36 ms 38596 KB Output is correct
19 Correct 39 ms 38496 KB Output is correct
20 Correct 38 ms 38472 KB Output is correct
21 Correct 37 ms 38600 KB Output is correct
22 Correct 24 ms 28496 KB Output is correct
23 Correct 37 ms 38596 KB Output is correct
24 Correct 39 ms 38600 KB Output is correct
25 Correct 46 ms 38600 KB Output is correct
26 Correct 41 ms 38600 KB Output is correct
27 Correct 38 ms 38512 KB Output is correct
28 Correct 37 ms 38600 KB Output is correct
29 Correct 39 ms 38632 KB Output is correct
30 Correct 38 ms 38592 KB Output is correct
31 Correct 38 ms 38600 KB Output is correct
32 Correct 38 ms 38520 KB Output is correct
33 Correct 37 ms 38612 KB Output is correct
34 Correct 36 ms 38504 KB Output is correct
35 Correct 30 ms 32988 KB Output is correct
36 Correct 37 ms 38600 KB Output is correct
37 Correct 37 ms 38600 KB Output is correct
38 Correct 38 ms 38600 KB Output is correct
39 Correct 45 ms 38552 KB Output is correct
40 Correct 39 ms 38588 KB Output is correct
41 Correct 43 ms 38588 KB Output is correct
42 Correct 38 ms 38600 KB Output is correct
43 Correct 37 ms 38600 KB Output is correct
44 Correct 36 ms 38520 KB Output is correct
45 Correct 38 ms 38660 KB Output is correct
46 Correct 618 ms 358400 KB Output is correct
47 Correct 948 ms 535624 KB Output is correct
48 Correct 1056 ms 535564 KB Output is correct
49 Correct 1044 ms 535604 KB Output is correct
50 Correct 1048 ms 535560 KB Output is correct
51 Correct 1002 ms 535464 KB Output is correct
52 Correct 1002 ms 535544 KB Output is correct
53 Correct 636 ms 538444 KB Output is correct
54 Correct 1040 ms 535616 KB Output is correct
55 Correct 634 ms 531876 KB Output is correct
56 Correct 929 ms 535588 KB Output is correct
57 Correct 958 ms 535576 KB Output is correct
58 Correct 995 ms 535524 KB Output is correct
59 Correct 1016 ms 535512 KB Output is correct
60 Correct 1034 ms 535632 KB Output is correct
61 Correct 675 ms 538512 KB Output is correct
62 Correct 1030 ms 535568 KB Output is correct
63 Correct 1020 ms 535544 KB Output is correct
64 Correct 1008 ms 535564 KB Output is correct
65 Correct 966 ms 535640 KB Output is correct
66 Correct 618 ms 534636 KB Output is correct
67 Correct 956 ms 518372 KB Output is correct
68 Correct 1014 ms 535708 KB Output is correct
69 Correct 1030 ms 535512 KB Output is correct
70 Correct 998 ms 535716 KB Output is correct
71 Correct 984 ms 535504 KB Output is correct
72 Correct 963 ms 535620 KB Output is correct
73 Correct 1008 ms 535504 KB Output is correct
74 Correct 614 ms 538512 KB Output is correct
75 Correct 955 ms 535496 KB Output is correct
76 Correct 624 ms 536416 KB Output is correct
77 Correct 923 ms 535716 KB Output is correct
78 Correct 2354 ms 532064 KB Output is correct
79 Correct 2558 ms 535684 KB Output is correct
80 Correct 2629 ms 535612 KB Output is correct
81 Correct 2629 ms 535584 KB Output is correct
82 Correct 2520 ms 535656 KB Output is correct
83 Correct 2594 ms 535604 KB Output is correct
84 Correct 2490 ms 535744 KB Output is correct
85 Correct 2081 ms 538624 KB Output is correct
86 Correct 2289 ms 535596 KB Output is correct
87 Correct 2125 ms 535504 KB Output is correct
88 Correct 2486 ms 535496 KB Output is correct
89 Correct 2260 ms 538500 KB Output is correct
90 Correct 2256 ms 535568 KB Output is correct
91 Correct 24 ms 28444 KB Output is correct
92 Correct 42 ms 38596 KB Output is correct
93 Correct 39 ms 38616 KB Output is correct
94 Correct 944 ms 535628 KB Output is correct
95 Correct 992 ms 535548 KB Output is correct
96 Correct 1026 ms 535664 KB Output is correct
97 Correct 935 ms 535592 KB Output is correct
98 Correct 630 ms 538576 KB Output is correct
99 Correct 967 ms 535580 KB Output is correct
100 Correct 1002 ms 535488 KB Output is correct
101 Correct 998 ms 535760 KB Output is correct
102 Correct 899 ms 535660 KB Output is correct
103 Correct 646 ms 534780 KB Output is correct
104 Correct 38 ms 38552 KB Output is correct
105 Correct 37 ms 38528 KB Output is correct
106 Correct 38 ms 38560 KB Output is correct
107 Correct 37 ms 38524 KB Output is correct
108 Correct 37 ms 38600 KB Output is correct
109 Correct 40 ms 38600 KB Output is correct
110 Correct 39 ms 38512 KB Output is correct
111 Correct 40 ms 38620 KB Output is correct
112 Correct 37 ms 38600 KB Output is correct
113 Correct 37 ms 38600 KB Output is correct
114 Correct 610 ms 150048 KB Output is correct
115 Correct 2295 ms 535520 KB Output is correct
116 Correct 2327 ms 535616 KB Output is correct
117 Correct 2336 ms 535624 KB Output is correct
118 Correct 2390 ms 535672 KB Output is correct
119 Correct 2398 ms 535600 KB Output is correct
120 Correct 2160 ms 535548 KB Output is correct
121 Correct 1691 ms 538416 KB Output is correct
122 Correct 1797 ms 535636 KB Output is correct
123 Correct 1716 ms 538492 KB Output is correct
124 Correct 2143 ms 535644 KB Output is correct
125 Correct 938 ms 535568 KB Output is correct
126 Correct 1002 ms 535708 KB Output is correct
127 Correct 1027 ms 535696 KB Output is correct
128 Correct 925 ms 535512 KB Output is correct
129 Correct 706 ms 534576 KB Output is correct
130 Correct 960 ms 518388 KB Output is correct
131 Correct 1051 ms 535628 KB Output is correct
132 Correct 1094 ms 535788 KB Output is correct
133 Correct 1065 ms 535584 KB Output is correct
134 Correct 1078 ms 535552 KB Output is correct
135 Correct 1012 ms 535600 KB Output is correct
136 Correct 1022 ms 535592 KB Output is correct
137 Correct 613 ms 538432 KB Output is correct
138 Correct 910 ms 535644 KB Output is correct
139 Correct 628 ms 536380 KB Output is correct
140 Correct 969 ms 535612 KB Output is correct
141 Correct 39 ms 38592 KB Output is correct
142 Correct 39 ms 38600 KB Output is correct
143 Correct 41 ms 38568 KB Output is correct
144 Correct 38 ms 38492 KB Output is correct
145 Correct 37 ms 38600 KB Output is correct
146 Correct 31 ms 33012 KB Output is correct
147 Correct 43 ms 38572 KB Output is correct
148 Correct 39 ms 38508 KB Output is correct
149 Correct 38 ms 38524 KB Output is correct
150 Correct 39 ms 38600 KB Output is correct
151 Correct 38 ms 38512 KB Output is correct
152 Correct 38 ms 38500 KB Output is correct
153 Correct 37 ms 38600 KB Output is correct
154 Correct 38 ms 38596 KB Output is correct
155 Correct 38 ms 38536 KB Output is correct
156 Correct 38 ms 38524 KB Output is correct
157 Correct 2214 ms 478808 KB Output is correct
158 Correct 2397 ms 535740 KB Output is correct
159 Correct 2648 ms 535744 KB Output is correct
160 Correct 2483 ms 535552 KB Output is correct
161 Correct 2706 ms 535756 KB Output is correct
162 Correct 2721 ms 535588 KB Output is correct
163 Correct 2581 ms 535564 KB Output is correct
164 Correct 2110 ms 538440 KB Output is correct
165 Correct 2130 ms 535756 KB Output is correct
166 Correct 2056 ms 538636 KB Output is correct
167 Correct 2325 ms 535608 KB Output is correct
168 Correct 25 ms 28496 KB Output is correct
169 Correct 1570 ms 204412 KB Output is correct
170 Correct 2773 ms 535580 KB Output is correct
171 Correct 3023 ms 535560 KB Output is correct
172 Correct 2825 ms 535668 KB Output is correct
173 Correct 2830 ms 535656 KB Output is correct
174 Correct 2950 ms 535604 KB Output is correct
175 Correct 3000 ms 535496 KB Output is correct
176 Correct 1953 ms 538668 KB Output is correct
177 Correct 2203 ms 535600 KB Output is correct
178 Correct 2147 ms 537256 KB Output is correct
179 Correct 2424 ms 535704 KB Output is correct