oj.uz

Submission #758656

# Submission time Handle Problem Language Result Execution time Memory
758656 2023-06-15T05:13:37 Z scanhex Segments (IZhO18_segments) C++17
75 / 100
 3542 ms 41892 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(const vector<pair<int,int>>& pts) {
		xs.clear();
		xs.reserve(pts.size());
		for (auto& p : pts) 
			xs.push_back(p.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 (const auto& p : pts) {
			preadd(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(), p.second);
			//all.add(p.second);
		}
		for (int i = 0; i <= xs.size(); ++i) 
			v[i].preaddfinish();
		for (const auto& p : pts) {
			add(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(), p.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 {
	vector<pair<int,int>> all;
	vector<pair<int,int>> block;
	vector<pair<int,int>> erblock;
	vector<pair<int, int>> newall;
	static2d st;

	void check_rebuild() {
		if (block.size() + erblock.size() >= BL) {
			sort(block.begin(), block.end(), ycmp);
			newall.resize(all.size() + block.size());
			merge(all.begin(), all.end(), block.begin(), block.end(), newall.begin(), ycmp);
			sort(erblock.begin(), erblock.end(), ycmp);
			all.clear();
			int ptr = 0; 
			for (auto x : erblock) {
				 while (ptr < newall.size() && ycmp(newall[ptr], x))
					 all.push_back(newall[ptr++]);
				 // always true? 
				 ++ptr;
			}
			while (ptr < newall.size())
				all.push_back(newall[ptr++]);
			block.clear();
			erblock.clear();
			st.build(all);
		}
	}
	
	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(const std::vector<std::pair<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:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 0; i <= xs.size(); ++i)
      |                   ~~^~~~~~~~~~~~
segments.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (int i = 0; i <= xs.size(); ++i)
      |                   ~~^~~~~~~~~~~~
segments.cpp: In member function 'int static2d::get(int, int, int)':
segments.cpp:115:7: warning: unused variable 'xrr' [-Wunused-variable]
  115 |   int xrr = xr;
      |       ^~~
segments.cpp: In member function 'void rofl2d::check_rebuild()':
segments.cpp:149:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |      while (ptr < newall.size() && ycmp(newall[ptr], x))
      |             ~~~~^~~~~~~~~~~~~~~
segments.cpp:154:15: 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 |    while (ptr < newall.size())
      |           ~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 8 ms 6612 KB Output is correct
4 Correct 8 ms 6696 KB Output is correct
5 Correct 8 ms 7172 KB Output is correct
6 Correct 10 ms 6732 KB Output is correct
7 Correct 8 ms 6684 KB Output is correct
8 Correct 9 ms 6988 KB Output is correct
9 Correct 11 ms 6964 KB Output is correct
10 Correct 6 ms 7252 KB Output is correct
11 Correct 14 ms 6612 KB Output is correct
12 Correct 13 ms 6612 KB Output is correct
13 Correct 8 ms 7212 KB Output is correct
14 Correct 9 ms 6960 KB Output is correct
15 Correct 8 ms 6696 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 8 ms 6724 KB Output is correct
18 Correct 7 ms 7240 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct
20 Correct 8 ms 6740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 14496 KB Output is correct
2 Correct 516 ms 14404 KB Output is correct
3 Correct 482 ms 14420 KB Output is correct
4 Correct 562 ms 15136 KB Output is correct
5 Correct 818 ms 21952 KB Output is correct
6 Correct 838 ms 22392 KB Output is correct
7 Correct 523 ms 14464 KB Output is correct
8 Correct 480 ms 14424 KB Output is correct
9 Correct 492 ms 14480 KB Output is correct
10 Correct 604 ms 9460 KB Output is correct
11 Correct 566 ms 10692 KB Output is correct
12 Correct 581 ms 17988 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 7448 KB Output is correct
2 Correct 132 ms 7404 KB Output is correct
3 Correct 137 ms 7412 KB Output is correct
4 Correct 132 ms 7452 KB Output is correct
5 Correct 583 ms 17988 KB Output is correct
6 Correct 403 ms 16324 KB Output is correct
7 Correct 495 ms 17300 KB Output is correct
8 Correct 799 ms 21912 KB Output is correct
9 Correct 821 ms 21844 KB Output is correct
10 Correct 675 ms 17492 KB Output is correct
11 Correct 181 ms 8076 KB Output is correct
12 Correct 678 ms 17836 KB Output is correct
13 Correct 589 ms 16764 KB Output is correct
14 Correct 377 ms 11604 KB Output is correct
15 Correct 335 ms 10792 KB Output is correct
16 Correct 279 ms 9800 KB Output is correct
17 Correct 412 ms 14528 KB Output is correct
18 Correct 417 ms 14400 KB Output is correct
19 Correct 428 ms 14416 KB Output is correct
20 Correct 412 ms 14468 KB Output is correct
21 Correct 186 ms 8156 KB Output is correct
22 Correct 437 ms 12764 KB Output is correct
23 Correct 553 ms 15428 KB Output is correct
24 Correct 464 ms 13212 KB Output is correct
25 Correct 135 ms 7528 KB Output is correct
26 Correct 133 ms 7488 KB Output is correct
27 Correct 135 ms 7420 KB Output is correct
28 Correct 139 ms 7428 KB Output is correct
29 Correct 582 ms 16004 KB Output is correct
30 Correct 591 ms 16288 KB Output is correct
31 Correct 847 ms 21948 KB Output is correct
32 Correct 709 ms 17608 KB Output is correct
33 Correct 600 ms 16928 KB Output is correct
34 Correct 324 ms 10736 KB Output is correct
35 Correct 525 ms 14796 KB Output is correct
36 Correct 606 ms 17256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7444 KB Output is correct
2 Correct 135 ms 7444 KB Output is correct
3 Correct 137 ms 7412 KB Output is correct
4 Correct 139 ms 7444 KB Output is correct
5 Correct 651 ms 19436 KB Output is correct
6 Correct 410 ms 8872 KB Output is correct
7 Correct 692 ms 19804 KB Output is correct
8 Correct 302 ms 10036 KB Output is correct
9 Correct 444 ms 12704 KB Output is correct
10 Correct 744 ms 18860 KB Output is correct
11 Correct 275 ms 9184 KB Output is correct
12 Correct 833 ms 22360 KB Output is correct
13 Correct 608 ms 16364 KB Output is correct
14 Correct 432 ms 11884 KB Output is correct
15 Correct 834 ms 21848 KB Output is correct
16 Correct 637 ms 17216 KB Output is correct
17 Correct 484 ms 14480 KB Output is correct
18 Correct 483 ms 14424 KB Output is correct
19 Correct 475 ms 14420 KB Output is correct
20 Correct 492 ms 14380 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 8 ms 6612 KB Output is correct
4 Correct 8 ms 6696 KB Output is correct
5 Correct 8 ms 7172 KB Output is correct
6 Correct 10 ms 6732 KB Output is correct
7 Correct 8 ms 6684 KB Output is correct
8 Correct 9 ms 6988 KB Output is correct
9 Correct 11 ms 6964 KB Output is correct
10 Correct 6 ms 7252 KB Output is correct
11 Correct 14 ms 6612 KB Output is correct
12 Correct 13 ms 6612 KB Output is correct
13 Correct 8 ms 7212 KB Output is correct
14 Correct 9 ms 6960 KB Output is correct
15 Correct 8 ms 6696 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 8 ms 6724 KB Output is correct
18 Correct 7 ms 7240 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct
20 Correct 8 ms 6740 KB Output is correct
21 Correct 493 ms 14496 KB Output is correct
22 Correct 516 ms 14404 KB Output is correct
23 Correct 482 ms 14420 KB Output is correct
24 Correct 562 ms 15136 KB Output is correct
25 Correct 818 ms 21952 KB Output is correct
26 Correct 838 ms 22392 KB Output is correct
27 Correct 523 ms 14464 KB Output is correct
28 Correct 480 ms 14424 KB Output is correct
29 Correct 492 ms 14480 KB Output is correct
30 Correct 604 ms 9460 KB Output is correct
31 Correct 566 ms 10692 KB Output is correct
32 Correct 581 ms 17988 KB Output is correct
33 Correct 139 ms 7444 KB Output is correct
34 Correct 135 ms 7444 KB Output is correct
35 Correct 137 ms 7412 KB Output is correct
36 Correct 139 ms 7444 KB Output is correct
37 Correct 651 ms 19436 KB Output is correct
38 Correct 410 ms 8872 KB Output is correct
39 Correct 692 ms 19804 KB Output is correct
40 Correct 302 ms 10036 KB Output is correct
41 Correct 444 ms 12704 KB Output is correct
42 Correct 744 ms 18860 KB Output is correct
43 Correct 275 ms 9184 KB Output is correct
44 Correct 833 ms 22360 KB Output is correct
45 Correct 608 ms 16364 KB Output is correct
46 Correct 432 ms 11884 KB Output is correct
47 Correct 834 ms 21848 KB Output is correct
48 Correct 637 ms 17216 KB Output is correct
49 Correct 484 ms 14480 KB Output is correct
50 Correct 483 ms 14424 KB Output is correct
51 Correct 475 ms 14420 KB Output is correct
52 Correct 492 ms 14380 KB Output is correct
53 Correct 142 ms 7488 KB Output is correct
54 Correct 146 ms 7576 KB Output is correct
55 Correct 135 ms 7432 KB Output is correct
56 Correct 137 ms 7432 KB Output is correct
57 Correct 668 ms 11360 KB Output is correct
58 Correct 315 ms 8264 KB Output is correct
59 Correct 492 ms 16404 KB Output is correct
60 Correct 622 ms 7744 KB Output is correct
61 Correct 627 ms 16640 KB Output is correct
62 Correct 808 ms 21344 KB Output is correct
63 Correct 832 ms 22364 KB Output is correct
64 Correct 769 ms 21364 KB Output is correct
65 Correct 324 ms 10040 KB Output is correct
66 Correct 290 ms 9612 KB Output is correct
67 Correct 636 ms 17316 KB Output is correct
68 Correct 542 ms 14572 KB Output is correct
69 Correct 483 ms 14456 KB Output is correct
70 Correct 486 ms 14400 KB Output is correct
71 Correct 487 ms 14492 KB Output is correct
72 Correct 504 ms 14456 KB Output is correct
73 Correct 361 ms 10696 KB Output is correct
74 Correct 586 ms 14532 KB Output is correct
75 Correct 819 ms 22364 KB Output is correct
76 Correct 827 ms 22340 KB Output is correct
77 Correct 139 ms 7440 KB Output is correct
78 Correct 137 ms 7516 KB Output is correct
79 Correct 141 ms 7508 KB Output is correct
80 Correct 140 ms 7468 KB Output is correct
81 Correct 531 ms 14116 KB Output is correct
82 Correct 360 ms 10756 KB Output is correct
83 Correct 259 ms 9040 KB Output is correct
84 Correct 546 ms 14416 KB Output is correct
85 Correct 658 ms 17496 KB Output is correct
86 Correct 679 ms 18424 KB Output is correct
87 Correct 444 ms 12556 KB Output is correct
88 Correct 267 ms 9160 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 8 ms 6612 KB Output is correct
4 Correct 8 ms 6696 KB Output is correct
5 Correct 8 ms 7172 KB Output is correct
6 Correct 10 ms 6732 KB Output is correct
7 Correct 8 ms 6684 KB Output is correct
8 Correct 9 ms 6988 KB Output is correct
9 Correct 11 ms 6964 KB Output is correct
10 Correct 6 ms 7252 KB Output is correct
11 Correct 14 ms 6612 KB Output is correct
12 Correct 13 ms 6612 KB Output is correct
13 Correct 8 ms 7212 KB Output is correct
14 Correct 9 ms 6960 KB Output is correct
15 Correct 8 ms 6696 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 8 ms 6724 KB Output is correct
18 Correct 7 ms 7240 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct
20 Correct 8 ms 6740 KB Output is correct
21 Correct 493 ms 14496 KB Output is correct
22 Correct 516 ms 14404 KB Output is correct
23 Correct 482 ms 14420 KB Output is correct
24 Correct 562 ms 15136 KB Output is correct
25 Correct 818 ms 21952 KB Output is correct
26 Correct 838 ms 22392 KB Output is correct
27 Correct 523 ms 14464 KB Output is correct
28 Correct 480 ms 14424 KB Output is correct
29 Correct 492 ms 14480 KB Output is correct
30 Correct 604 ms 9460 KB Output is correct
31 Correct 566 ms 10692 KB Output is correct
32 Correct 581 ms 17988 KB Output is correct
33 Correct 150 ms 7448 KB Output is correct
34 Correct 132 ms 7404 KB Output is correct
35 Correct 137 ms 7412 KB Output is correct
36 Correct 132 ms 7452 KB Output is correct
37 Correct 583 ms 17988 KB Output is correct
38 Correct 403 ms 16324 KB Output is correct
39 Correct 495 ms 17300 KB Output is correct
40 Correct 799 ms 21912 KB Output is correct
41 Correct 821 ms 21844 KB Output is correct
42 Correct 675 ms 17492 KB Output is correct
43 Correct 181 ms 8076 KB Output is correct
44 Correct 678 ms 17836 KB Output is correct
45 Correct 589 ms 16764 KB Output is correct
46 Correct 377 ms 11604 KB Output is correct
47 Correct 335 ms 10792 KB Output is correct
48 Correct 279 ms 9800 KB Output is correct
49 Correct 412 ms 14528 KB Output is correct
50 Correct 417 ms 14400 KB Output is correct
51 Correct 428 ms 14416 KB Output is correct
52 Correct 412 ms 14468 KB Output is correct
53 Correct 186 ms 8156 KB Output is correct
54 Correct 437 ms 12764 KB Output is correct
55 Correct 553 ms 15428 KB Output is correct
56 Correct 464 ms 13212 KB Output is correct
57 Correct 135 ms 7528 KB Output is correct
58 Correct 133 ms 7488 KB Output is correct
59 Correct 135 ms 7420 KB Output is correct
60 Correct 139 ms 7428 KB Output is correct
61 Correct 582 ms 16004 KB Output is correct
62 Correct 591 ms 16288 KB Output is correct
63 Correct 847 ms 21948 KB Output is correct
64 Correct 709 ms 17608 KB Output is correct
65 Correct 600 ms 16928 KB Output is correct
66 Correct 324 ms 10736 KB Output is correct
67 Correct 525 ms 14796 KB Output is correct
68 Correct 606 ms 17256 KB Output is correct
69 Correct 139 ms 7444 KB Output is correct
70 Correct 135 ms 7444 KB Output is correct
71 Correct 137 ms 7412 KB Output is correct
72 Correct 139 ms 7444 KB Output is correct
73 Correct 651 ms 19436 KB Output is correct
74 Correct 410 ms 8872 KB Output is correct
75 Correct 692 ms 19804 KB Output is correct
76 Correct 302 ms 10036 KB Output is correct
77 Correct 444 ms 12704 KB Output is correct
78 Correct 744 ms 18860 KB Output is correct
79 Correct 275 ms 9184 KB Output is correct
80 Correct 833 ms 22360 KB Output is correct
81 Correct 608 ms 16364 KB Output is correct
82 Correct 432 ms 11884 KB Output is correct
83 Correct 834 ms 21848 KB Output is correct
84 Correct 637 ms 17216 KB Output is correct
85 Correct 484 ms 14480 KB Output is correct
86 Correct 483 ms 14424 KB Output is correct
87 Correct 475 ms 14420 KB Output is correct
88 Correct 492 ms 14380 KB Output is correct
89 Correct 142 ms 7488 KB Output is correct
90 Correct 146 ms 7576 KB Output is correct
91 Correct 135 ms 7432 KB Output is correct
92 Correct 137 ms 7432 KB Output is correct
93 Correct 668 ms 11360 KB Output is correct
94 Correct 315 ms 8264 KB Output is correct
95 Correct 492 ms 16404 KB Output is correct
96 Correct 622 ms 7744 KB Output is correct
97 Correct 627 ms 16640 KB Output is correct
98 Correct 808 ms 21344 KB Output is correct
99 Correct 832 ms 22364 KB Output is correct
100 Correct 769 ms 21364 KB Output is correct
101 Correct 324 ms 10040 KB Output is correct
102 Correct 290 ms 9612 KB Output is correct
103 Correct 636 ms 17316 KB Output is correct
104 Correct 542 ms 14572 KB Output is correct
105 Correct 483 ms 14456 KB Output is correct
106 Correct 486 ms 14400 KB Output is correct
107 Correct 487 ms 14492 KB Output is correct
108 Correct 504 ms 14456 KB Output is correct
109 Correct 361 ms 10696 KB Output is correct
110 Correct 586 ms 14532 KB Output is correct
111 Correct 819 ms 22364 KB Output is correct
112 Correct 827 ms 22340 KB Output is correct
113 Correct 139 ms 7440 KB Output is correct
114 Correct 137 ms 7516 KB Output is correct
115 Correct 141 ms 7508 KB Output is correct
116 Correct 140 ms 7468 KB Output is correct
117 Correct 531 ms 14116 KB Output is correct
118 Correct 360 ms 10756 KB Output is correct
119 Correct 259 ms 9040 KB Output is correct
120 Correct 546 ms 14416 KB Output is correct
121 Correct 658 ms 17496 KB Output is correct
122 Correct 679 ms 18424 KB Output is correct
123 Correct 444 ms 12556 KB Output is correct
124 Correct 267 ms 9160 KB Output is correct
125 Correct 292 ms 8080 KB Output is correct
126 Correct 280 ms 8064 KB Output is correct
127 Correct 342 ms 8184 KB Output is correct
128 Correct 282 ms 8052 KB Output is correct
129 Correct 281 ms 8036 KB Output is correct
130 Correct 285 ms 8128 KB Output is correct
131 Correct 1438 ms 10056 KB Output is correct
132 Correct 1576 ms 21272 KB Output is correct
133 Correct 2001 ms 28772 KB Output is correct
134 Correct 659 ms 12360 KB Output is correct
135 Correct 2237 ms 30440 KB Output is correct
136 Correct 1054 ms 7592 KB Output is correct
137 Correct 3542 ms 37352 KB Output is correct
138 Correct 2366 ms 26036 KB Output is correct
139 Correct 2956 ms 31684 KB Output is correct
140 Correct 3345 ms 35728 KB Output is correct
141 Correct 2592 ms 28672 KB Output is correct
142 Correct 538 ms 9752 KB Output is correct
143 Correct 1012 ms 13628 KB Output is correct
144 Correct 422 ms 8912 KB Output is correct
145 Correct 3193 ms 35104 KB Output is correct
146 Correct 1550 ms 23160 KB Output is correct
147 Correct 1054 ms 18224 KB Output is correct
148 Correct 964 ms 17664 KB Output is correct
149 Correct 1722 ms 28552 KB Output is correct
150 Correct 1165 ms 29264 KB Output is correct
151 Correct 1696 ms 28420 KB Output is correct
152 Correct 1734 ms 28464 KB Output is correct
153 Correct 1156 ms 28884 KB Output is correct
154 Correct 1708 ms 28616 KB Output is correct
155 Correct 722 ms 15068 KB Output is correct
156 Correct 1123 ms 18768 KB Output is correct
157 Correct 3292 ms 40160 KB Output is correct
158 Runtime error 3290 ms 41892 KB Memory limit exceeded
159 Halted 0 ms 0 KB -