oj.uz

Submission #758668

# Submission time Handle Problem Language Result Execution time Memory
758668 2023-06-15T05:32:47 Z scanhex Segments (IZhO18_segments) C++17
100 / 100
 4091 ms 39336 KB 
#include <bits/stdc++.h>

using namespace std;
using nagai = long long;

struct dss {
	vector<pair<int,int>> segs;
	void insert(int l, int r) {
		segs.push_back({l, r});
	}
	int get(int l, int r, int k) {
		if (k == 0) return segs.size();
		int res = 0;
		for (auto& x : segs) {
			int ll = max(x.first, l), rr = min(x.second, r); 
			if (rr - ll + 1 >= k)
				++res;
		}
		return res;
	}
};

const int oo = 0x3f3f3f3f;
 
struct static1d {
	int* coords = nullptr;
	int cnt = 0;
	void clear() {
		if (coords)
			delete[] coords;
		cnt = 0;
	}

	void preadd(int c) {
		++cnt;
	}

	void preaddfinish() {
		coords = new int[cnt];
		cnt = 0;
	}

	void add(int c) {
		coords[cnt++] = c;
	}

	void finalize() {
	}

	int get(int l, int r) {
		if (l > r) return 0;
		auto itr = upper_bound(coords, coords + cnt, r);
		auto itl = lower_bound(coords, coords + cnt, l);
		//cerr << "coords\n";
		//for(auto& x : coords) 
			//cerr << x << ' ';
		//cerr << '\n';
		//cerr << l << ' ' << r << ' ' << itr - itl << '\n';
		return itr - itl;
	}
};

bool ycmp(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second)
		return a.second < b.second;
	return a.first < b.first;
}

const int N=200200;

struct static2d {
	static1d v[N];
	//static1d all;
	vector<int> xs;

	void preadd(int x, int y) {
		for (++x; x <= xs.size(); x = (x | x - 1) + 1)
			v[x].preadd(y);
	}

	void add(int x, int y) {
		for (++x; x <= xs.size(); x = (x | x - 1) + 1)
			v[x].add(y);
	}

	void build(pair<int,int>* pts, int sz) {
		xs.clear();
		xs.reserve(sz);
		for (int i = 0; i < sz; ++i) 
			xs.push_back(pts[i].first);
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		for (int i = 0; i < xs.size() + 1; ++i) 
			v[i].clear();
		for (int i = 0; i < sz; ++i) 
			preadd(lower_bound(xs.begin(), xs.end(), pts[i].first) - xs.begin(), pts[i].second);
		for (int i = 0; i <= xs.size(); ++i) 
			v[i].preaddfinish();
		for (int i = 0; i < sz; ++i)
			add(lower_bound(xs.begin(), xs.end(), pts[i].first) - xs.begin(), pts[i].second);
			//all.add(p.second);
		for (int i = 0; i <= xs.size(); ++i) 
			v[i].finalize();
		//all.finalize();
	}

	int get(int xr, int y1, int y2) {
		//if (xr == oo) 
			//return all.get(y1, y2);
		if (xr < 0) return 0;
		++xr;
		int xrr = xr;
		xr = lower_bound(xs.begin(), xs.end(), xr) - xs.begin();
		int res = 0;
		for (; xr; xr &= xr - 1) 
			res += v[xr].get(y1, y2);
		//cerr << xrr << ' ' << y1 << ' ' << y2 << ' ' << res << '\n';
		return res;
	}

	// all inclusive
	int get(int x1, int x2, int y1, int y2) {
		if (x1 > x2) return 0;
		return get(x2, y1, y2) - get(x1 - 1, y1, y2);
	}
};

const int BL = 4000;

struct rofl2d {
	pair<int,int>* all;
	vector<pair<int,int>> block;
	vector<pair<int,int>> erblock;
	//pair<int, int>* newall;
	int call = 0, cnewall = 0;
	static2d st;

	rofl2d() {
		all = new pair<int, int>[N];
		//newall = new pair<int, int>[N];
	}

	void check_rebuild() {
		if (block.size() + erblock.size() >= BL) {
			sort(block.begin(), block.end(), ycmp);
			for (auto x : block) 
				all[call++] = x;
			sort(all, all + call, ycmp);
			//cnewall = call + block.size();
			sort(erblock.begin(), erblock.end(), ycmp);
			int ptr = 0; 
			int eptr = 0;
			for (int i = 0; i < call; ++i) {
				if (eptr < erblock.size() && erblock[eptr] == all[i])
					++eptr;
				else
					all[ptr++] = all[i];
			}
			call = ptr;
			block.clear();
			erblock.clear();
			st.build(all, call);
		}
	}
	
	void insert(int x, int y) {
		block.push_back({x, y});
		check_rebuild();
	}

	void erase(int x, int y) {
		erblock.push_back({x, y});
		check_rebuild();
	}

	int get(int x1, int x2, int y1, int y2) {
		int res = st.get(x1, x2, y1, y2);
		/*
		for (auto p : block) 
			if (x1 <= p.first && p.first <= x2 && y1 <= p.second && p.second <= y2) 
				++res;
		for (auto p : erblock) 
			if (x1 <= p.first && p.first <= x2 && y1 <= p.second && p.second <= y2) 
				--res;
				*/
		return res;
	}
};


struct ds {
	int tot = 0;
	rofl2d rofl_l, rofl_r;
	void insert(int l, int r) {
		++tot;
		rofl_l.insert(l, r - l);
		rofl_r.insert(r, r - l);
		//rofl_len.insert(0, r - l);
	}
	void erase(int l, int r) {
		--tot;
		rofl_l.erase(l, r - l);
		rofl_r.erase(r, r - l);
		//rofl_len.erase(0, r - l);
	}
	int get(int l, int r, int k) {
		if (r - l + 1 < k) return 0;
		if (k == 0) return tot;
		int res = tot - rofl_l.block.size() + rofl_l.erblock.size();
		for (auto p : rofl_l.block) {
			int ll = max(p.first, l); 
			int rr = min(p.first + p.second, r);
			if (rr - ll + 1 >= k) 
				++res;
		}
		for (auto p : rofl_l.erblock) {
			int ll = max(p.first, l); 
			int rr = min(p.first + p.second, r);
			if (rr - ll + 1 >= k) 
				--res;
		}
		//cerr << "rofl_l" << '\n';
		res -= rofl_l.get(r - k + 2, oo, k - 1, oo);
		//cerr << "rofl_r" << '\n';
		res -= rofl_r.get(0, l + k - 2, k - 1, oo);
		//cerr << "rofl_len" << '\n';
		res -= rofl_l.get(0, oo, 0, k - 2);
		return res;
	}
} add;

void stress() {
	int C = 5;
	for (int i = 0; i < 10000; ++i) {
		ds smart;
		dss stupid;
		stringstream ss;
		for (int i = 0; i < 10; ++i) {
			int x = rand() % C, y = rand() % C;
			if (x > y) swap(x, y);
			ss << "1 " << x << ' ' << y << '\n';
			smart.insert(x, y);
			stupid.insert(x, y);

			int a = rand() % C, b = rand() % C, k = rand() % C;
			if (a > b) swap(a, b);
			if (smart.get(a, b, k) != stupid.get(a, b, k)) {
				ss << smart.get(a, b, k) << ' ' << stupid.get(a, b, k) << '\n';
				ss << "3 " << a << ' ' << b << ' ' << k << '\n';
				cerr << ss.str();
				exit(1);
			}
		}
	}
	exit(0);
}


int main() {
	//stress();
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, t; 
	cin >> n >> t; 
	int lastans = 0;
	vector<pair<int, int>> segs;
	while (n--) {
		int tt;
		cin >> tt; 
		if (tt == 1) {
			int a, b;
			cin >> a >> b; 
			a ^= t * lastans;
			b ^= t * lastans;
			if (a > b) swap(a, b);
			segs.push_back({a, b});
			add.insert(a, b);
		}
		else if (tt == 2) {
			int id; 
			cin >> id; 
			--id;
			add.erase(segs[id].first, segs[id].second);
		}
		else {
			int a, b, k;
			cin >> a >> b >> k;
			a ^= t * lastans;
			b ^= t * lastans;
			if (a > b) swap(a, b);
			lastans = add.get(a, b, k);
			cout << lastans << '\n';
		}
	}
}

Compilation message

segments.cpp: In member function 'void static2d::preadd(int, int)':
segments.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (++x; x <= xs.size(); x = (x | x - 1) + 1)
      |             ~~^~~~~~~~~~~~
segments.cpp:77:40: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   77 |   for (++x; x <= xs.size(); x = (x | x - 1) + 1)
      |                                      ~~^~~
segments.cpp: In member function 'void static2d::add(int, int)':
segments.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (++x; x <= xs.size(); x = (x | x - 1) + 1)
      |             ~~^~~~~~~~~~~~
segments.cpp:82:40: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   82 |   for (++x; x <= xs.size(); x = (x | x - 1) + 1)
      |                                      ~~^~~
segments.cpp: In member function 'void static2d::build(std::pair<int, int>*, int)':
segments.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i = 0; i < xs.size() + 1; ++i)
      |                   ~~^~~~~~~~~~~~~~~
segments.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = 0; i <= xs.size(); ++i)
      |                   ~~^~~~~~~~~~~~
segments.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int i = 0; i <= xs.size(); ++i)
      |                   ~~^~~~~~~~~~~~
segments.cpp: In member function 'int static2d::get(int, int, int)':
segments.cpp:112:7: warning: unused variable 'xrr' [-Wunused-variable]
  112 |   int xrr = xr;
      |       ^~~
segments.cpp: In member function 'void rofl2d::check_rebuild()':
segments.cpp:154:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     if (eptr < erblock.size() && erblock[eptr] == all[i])
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 9 ms 9776 KB Output is correct
4 Correct 9 ms 9780 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 14 ms 9812 KB Output is correct
7 Correct 10 ms 9868 KB Output is correct
8 Correct 11 ms 10096 KB Output is correct
9 Correct 10 ms 10040 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 15 ms 9868 KB Output is correct
12 Correct 15 ms 9772 KB Output is correct
13 Correct 8 ms 10196 KB Output is correct
14 Correct 12 ms 9992 KB Output is correct
15 Correct 9 ms 9812 KB Output is correct
16 Correct 9 ms 9760 KB Output is correct
17 Correct 10 ms 9984 KB Output is correct
18 Correct 11 ms 10196 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 10 ms 9812 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 16048 KB Output is correct
2 Correct 550 ms 16136 KB Output is correct
3 Correct 523 ms 16124 KB Output is correct
4 Correct 582 ms 16624 KB Output is correct
5 Correct 904 ms 22088 KB Output is correct
6 Correct 983 ms 22552 KB Output is correct
7 Correct 520 ms 16032 KB Output is correct
8 Correct 514 ms 16112 KB Output is correct
9 Correct 510 ms 16112 KB Output is correct
10 Correct 611 ms 12092 KB Output is correct
11 Correct 584 ms 13208 KB Output is correct
12 Correct 651 ms 18868 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 10428 KB Output is correct
2 Correct 138 ms 10440 KB Output is correct
3 Correct 142 ms 10476 KB Output is correct
4 Correct 137 ms 10544 KB Output is correct
5 Correct 660 ms 19164 KB Output is correct
6 Correct 451 ms 17520 KB Output is correct
7 Correct 546 ms 18416 KB Output is correct
8 Correct 901 ms 22188 KB Output is correct
9 Correct 964 ms 21840 KB Output is correct
10 Correct 802 ms 18488 KB Output is correct
11 Correct 178 ms 10920 KB Output is correct
12 Correct 787 ms 18828 KB Output is correct
13 Correct 693 ms 17924 KB Output is correct
14 Correct 414 ms 13832 KB Output is correct
15 Correct 380 ms 13252 KB Output is correct
16 Correct 304 ms 12332 KB Output is correct
17 Correct 455 ms 16180 KB Output is correct
18 Correct 461 ms 16064 KB Output is correct
19 Correct 488 ms 16020 KB Output is correct
20 Correct 481 ms 16096 KB Output is correct
21 Correct 203 ms 11128 KB Output is correct
22 Correct 541 ms 14804 KB Output is correct
23 Correct 643 ms 17008 KB Output is correct
24 Correct 536 ms 15144 KB Output is correct
25 Correct 155 ms 10440 KB Output is correct
26 Correct 141 ms 10508 KB Output is correct
27 Correct 140 ms 10472 KB Output is correct
28 Correct 138 ms 10440 KB Output is correct
29 Correct 700 ms 17408 KB Output is correct
30 Correct 694 ms 17708 KB Output is correct
31 Correct 964 ms 22296 KB Output is correct
32 Correct 792 ms 18560 KB Output is correct
33 Correct 695 ms 18132 KB Output is correct
34 Correct 370 ms 13124 KB Output is correct
35 Correct 605 ms 16312 KB Output is correct
36 Correct 732 ms 18392 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 10440 KB Output is correct
2 Correct 139 ms 10440 KB Output is correct
3 Correct 156 ms 10420 KB Output is correct
4 Correct 150 ms 10512 KB Output is correct
5 Correct 709 ms 20100 KB Output is correct
6 Correct 410 ms 11572 KB Output is correct
7 Correct 810 ms 20464 KB Output is correct
8 Correct 282 ms 12616 KB Output is correct
9 Correct 538 ms 14780 KB Output is correct
10 Correct 819 ms 19740 KB Output is correct
11 Correct 322 ms 11848 KB Output is correct
12 Correct 992 ms 22640 KB Output is correct
13 Correct 744 ms 17988 KB Output is correct
14 Correct 489 ms 14120 KB Output is correct
15 Correct 974 ms 21804 KB Output is correct
16 Correct 734 ms 18500 KB Output is correct
17 Correct 530 ms 16140 KB Output is correct
18 Correct 508 ms 16016 KB Output is correct
19 Correct 528 ms 16120 KB Output is correct
20 Correct 523 ms 16112 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 9 ms 9776 KB Output is correct
4 Correct 9 ms 9780 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 14 ms 9812 KB Output is correct
7 Correct 10 ms 9868 KB Output is correct
8 Correct 11 ms 10096 KB Output is correct
9 Correct 10 ms 10040 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 15 ms 9868 KB Output is correct
12 Correct 15 ms 9772 KB Output is correct
13 Correct 8 ms 10196 KB Output is correct
14 Correct 12 ms 9992 KB Output is correct
15 Correct 9 ms 9812 KB Output is correct
16 Correct 9 ms 9760 KB Output is correct
17 Correct 10 ms 9984 KB Output is correct
18 Correct 11 ms 10196 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 10 ms 9812 KB Output is correct
21 Correct 517 ms 16048 KB Output is correct
22 Correct 550 ms 16136 KB Output is correct
23 Correct 523 ms 16124 KB Output is correct
24 Correct 582 ms 16624 KB Output is correct
25 Correct 904 ms 22088 KB Output is correct
26 Correct 983 ms 22552 KB Output is correct
27 Correct 520 ms 16032 KB Output is correct
28 Correct 514 ms 16112 KB Output is correct
29 Correct 510 ms 16112 KB Output is correct
30 Correct 611 ms 12092 KB Output is correct
31 Correct 584 ms 13208 KB Output is correct
32 Correct 651 ms 18868 KB Output is correct
33 Correct 155 ms 10440 KB Output is correct
34 Correct 139 ms 10440 KB Output is correct
35 Correct 156 ms 10420 KB Output is correct
36 Correct 150 ms 10512 KB Output is correct
37 Correct 709 ms 20100 KB Output is correct
38 Correct 410 ms 11572 KB Output is correct
39 Correct 810 ms 20464 KB Output is correct
40 Correct 282 ms 12616 KB Output is correct
41 Correct 538 ms 14780 KB Output is correct
42 Correct 819 ms 19740 KB Output is correct
43 Correct 322 ms 11848 KB Output is correct
44 Correct 992 ms 22640 KB Output is correct
45 Correct 744 ms 17988 KB Output is correct
46 Correct 489 ms 14120 KB Output is correct
47 Correct 974 ms 21804 KB Output is correct
48 Correct 734 ms 18500 KB Output is correct
49 Correct 530 ms 16140 KB Output is correct
50 Correct 508 ms 16016 KB Output is correct
51 Correct 528 ms 16120 KB Output is correct
52 Correct 523 ms 16112 KB Output is correct
53 Correct 148 ms 10468 KB Output is correct
54 Correct 149 ms 10412 KB Output is correct
55 Correct 141 ms 10464 KB Output is correct
56 Correct 141 ms 10472 KB Output is correct
57 Correct 630 ms 13584 KB Output is correct
58 Correct 323 ms 11212 KB Output is correct
59 Correct 548 ms 17596 KB Output is correct
60 Correct 617 ms 10664 KB Output is correct
61 Correct 726 ms 17992 KB Output is correct
62 Correct 898 ms 21804 KB Output is correct
63 Correct 974 ms 22576 KB Output is correct
64 Correct 904 ms 22124 KB Output is correct
65 Correct 365 ms 12632 KB Output is correct
66 Correct 341 ms 12004 KB Output is correct
67 Correct 747 ms 18400 KB Output is correct
68 Correct 627 ms 16304 KB Output is correct
69 Correct 524 ms 16036 KB Output is correct
70 Correct 515 ms 16228 KB Output is correct
71 Correct 525 ms 16072 KB Output is correct
72 Correct 511 ms 16016 KB Output is correct
73 Correct 410 ms 13052 KB Output is correct
74 Correct 626 ms 16200 KB Output is correct
75 Correct 958 ms 22540 KB Output is correct
76 Correct 978 ms 22524 KB Output is correct
77 Correct 142 ms 10508 KB Output is correct
78 Correct 142 ms 10480 KB Output is correct
79 Correct 169 ms 10468 KB Output is correct
80 Correct 141 ms 10520 KB Output is correct
81 Correct 621 ms 15732 KB Output is correct
82 Correct 404 ms 13060 KB Output is correct
83 Correct 300 ms 11812 KB Output is correct
84 Correct 616 ms 16008 KB Output is correct
85 Correct 755 ms 18536 KB Output is correct
86 Correct 789 ms 19356 KB Output is correct
87 Correct 519 ms 14548 KB Output is correct
88 Correct 298 ms 11788 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 9 ms 9776 KB Output is correct
4 Correct 9 ms 9780 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 14 ms 9812 KB Output is correct
7 Correct 10 ms 9868 KB Output is correct
8 Correct 11 ms 10096 KB Output is correct
9 Correct 10 ms 10040 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 15 ms 9868 KB Output is correct
12 Correct 15 ms 9772 KB Output is correct
13 Correct 8 ms 10196 KB Output is correct
14 Correct 12 ms 9992 KB Output is correct
15 Correct 9 ms 9812 KB Output is correct
16 Correct 9 ms 9760 KB Output is correct
17 Correct 10 ms 9984 KB Output is correct
18 Correct 11 ms 10196 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 10 ms 9812 KB Output is correct
21 Correct 517 ms 16048 KB Output is correct
22 Correct 550 ms 16136 KB Output is correct
23 Correct 523 ms 16124 KB Output is correct
24 Correct 582 ms 16624 KB Output is correct
25 Correct 904 ms 22088 KB Output is correct
26 Correct 983 ms 22552 KB Output is correct
27 Correct 520 ms 16032 KB Output is correct
28 Correct 514 ms 16112 KB Output is correct
29 Correct 510 ms 16112 KB Output is correct
30 Correct 611 ms 12092 KB Output is correct
31 Correct 584 ms 13208 KB Output is correct
32 Correct 651 ms 18868 KB Output is correct
33 Correct 142 ms 10428 KB Output is correct
34 Correct 138 ms 10440 KB Output is correct
35 Correct 142 ms 10476 KB Output is correct
36 Correct 137 ms 10544 KB Output is correct
37 Correct 660 ms 19164 KB Output is correct
38 Correct 451 ms 17520 KB Output is correct
39 Correct 546 ms 18416 KB Output is correct
40 Correct 901 ms 22188 KB Output is correct
41 Correct 964 ms 21840 KB Output is correct
42 Correct 802 ms 18488 KB Output is correct
43 Correct 178 ms 10920 KB Output is correct
44 Correct 787 ms 18828 KB Output is correct
45 Correct 693 ms 17924 KB Output is correct
46 Correct 414 ms 13832 KB Output is correct
47 Correct 380 ms 13252 KB Output is correct
48 Correct 304 ms 12332 KB Output is correct
49 Correct 455 ms 16180 KB Output is correct
50 Correct 461 ms 16064 KB Output is correct
51 Correct 488 ms 16020 KB Output is correct
52 Correct 481 ms 16096 KB Output is correct
53 Correct 203 ms 11128 KB Output is correct
54 Correct 541 ms 14804 KB Output is correct
55 Correct 643 ms 17008 KB Output is correct
56 Correct 536 ms 15144 KB Output is correct
57 Correct 155 ms 10440 KB Output is correct
58 Correct 141 ms 10508 KB Output is correct
59 Correct 140 ms 10472 KB Output is correct
60 Correct 138 ms 10440 KB Output is correct
61 Correct 700 ms 17408 KB Output is correct
62 Correct 694 ms 17708 KB Output is correct
63 Correct 964 ms 22296 KB Output is correct
64 Correct 792 ms 18560 KB Output is correct
65 Correct 695 ms 18132 KB Output is correct
66 Correct 370 ms 13124 KB Output is correct
67 Correct 605 ms 16312 KB Output is correct
68 Correct 732 ms 18392 KB Output is correct
69 Correct 155 ms 10440 KB Output is correct
70 Correct 139 ms 10440 KB Output is correct
71 Correct 156 ms 10420 KB Output is correct
72 Correct 150 ms 10512 KB Output is correct
73 Correct 709 ms 20100 KB Output is correct
74 Correct 410 ms 11572 KB Output is correct
75 Correct 810 ms 20464 KB Output is correct
76 Correct 282 ms 12616 KB Output is correct
77 Correct 538 ms 14780 KB Output is correct
78 Correct 819 ms 19740 KB Output is correct
79 Correct 322 ms 11848 KB Output is correct
80 Correct 992 ms 22640 KB Output is correct
81 Correct 744 ms 17988 KB Output is correct
82 Correct 489 ms 14120 KB Output is correct
83 Correct 974 ms 21804 KB Output is correct
84 Correct 734 ms 18500 KB Output is correct
85 Correct 530 ms 16140 KB Output is correct
86 Correct 508 ms 16016 KB Output is correct
87 Correct 528 ms 16120 KB Output is correct
88 Correct 523 ms 16112 KB Output is correct
89 Correct 148 ms 10468 KB Output is correct
90 Correct 149 ms 10412 KB Output is correct
91 Correct 141 ms 10464 KB Output is correct
92 Correct 141 ms 10472 KB Output is correct
93 Correct 630 ms 13584 KB Output is correct
94 Correct 323 ms 11212 KB Output is correct
95 Correct 548 ms 17596 KB Output is correct
96 Correct 617 ms 10664 KB Output is correct
97 Correct 726 ms 17992 KB Output is correct
98 Correct 898 ms 21804 KB Output is correct
99 Correct 974 ms 22576 KB Output is correct
100 Correct 904 ms 22124 KB Output is correct
101 Correct 365 ms 12632 KB Output is correct
102 Correct 341 ms 12004 KB Output is correct
103 Correct 747 ms 18400 KB Output is correct
104 Correct 627 ms 16304 KB Output is correct
105 Correct 524 ms 16036 KB Output is correct
106 Correct 515 ms 16228 KB Output is correct
107 Correct 525 ms 16072 KB Output is correct
108 Correct 511 ms 16016 KB Output is correct
109 Correct 410 ms 13052 KB Output is correct
110 Correct 626 ms 16200 KB Output is correct
111 Correct 958 ms 22540 KB Output is correct
112 Correct 978 ms 22524 KB Output is correct
113 Correct 142 ms 10508 KB Output is correct
114 Correct 142 ms 10480 KB Output is correct
115 Correct 169 ms 10468 KB Output is correct
116 Correct 141 ms 10520 KB Output is correct
117 Correct 621 ms 15732 KB Output is correct
118 Correct 404 ms 13060 KB Output is correct
119 Correct 300 ms 11812 KB Output is correct
120 Correct 616 ms 16008 KB Output is correct
121 Correct 755 ms 18536 KB Output is correct
122 Correct 789 ms 19356 KB Output is correct
123 Correct 519 ms 14548 KB Output is correct
124 Correct 298 ms 11788 KB Output is correct
125 Correct 292 ms 11088 KB Output is correct
126 Correct 310 ms 11116 KB Output is correct
127 Correct 301 ms 11128 KB Output is correct
128 Correct 295 ms 11056 KB Output is correct
129 Correct 307 ms 11296 KB Output is correct
130 Correct 305 ms 11168 KB Output is correct
131 Correct 1451 ms 12532 KB Output is correct
132 Correct 1683 ms 21740 KB Output is correct
133 Correct 2239 ms 27780 KB Output is correct
134 Correct 664 ms 14496 KB Output is correct
135 Correct 2558 ms 29112 KB Output is correct
136 Correct 1054 ms 10704 KB Output is correct
137 Correct 4091 ms 34864 KB Output is correct
138 Correct 2809 ms 25968 KB Output is correct
139 Correct 3578 ms 30624 KB Output is correct
140 Correct 3886 ms 35260 KB Output is correct
141 Correct 3117 ms 28296 KB Output is correct
142 Correct 592 ms 12908 KB Output is correct
143 Correct 1194 ms 16144 KB Output is correct
144 Correct 474 ms 12212 KB Output is correct
145 Correct 3789 ms 33632 KB Output is correct
146 Correct 1784 ms 20340 KB Output is correct
147 Correct 1250 ms 16444 KB Output is correct
148 Correct 1103 ms 16100 KB Output is correct
149 Correct 1843 ms 23660 KB Output is correct
150 Correct 1306 ms 24484 KB Output is correct
151 Correct 1835 ms 23588 KB Output is correct
152 Correct 1846 ms 23664 KB Output is correct
153 Correct 1309 ms 24528 KB Output is correct
154 Correct 1841 ms 23744 KB Output is correct
155 Correct 807 ms 14212 KB Output is correct
156 Correct 1261 ms 16916 KB Output is correct
157 Correct 3832 ms 34456 KB Output is correct
158 Correct 3883 ms 34672 KB Output is correct
159 Correct 2795 ms 29220 KB Output is correct
160 Correct 1953 ms 22824 KB Output is correct
161 Correct 314 ms 13712 KB Output is correct
162 Correct 300 ms 13696 KB Output is correct
163 Correct 307 ms 13672 KB Output is correct
164 Correct 326 ms 13760 KB Output is correct
165 Correct 302 ms 13704 KB Output is correct
166 Correct 301 ms 13600 KB Output is correct
167 Correct 4021 ms 37656 KB Output is correct
168 Correct 4056 ms 39336 KB Output is correct
169 Correct 3820 ms 38540 KB Output is correct
170 Correct 3697 ms 36212 KB Output is correct
171 Correct 3032 ms 31108 KB Output is correct
172 Correct 1671 ms 22772 KB Output is correct
173 Correct 3775 ms 38400 KB Output is correct
174 Correct 1732 ms 23140 KB Output is correct
175 Correct 3143 ms 33696 KB Output is correct
176 Correct 1092 ms 19208 KB Output is correct
177 Correct 2724 ms 30396 KB Output is correct
178 Correct 2520 ms 29436 KB Output is correct