oj.uz

Submission #217449

# Submission time Handle Problem Language Result Execution time Memory
217449 2020-03-29T17:48:26 Z Toadologist Hamburg Steak (JOI20_hamburg) C++11
100 / 100
 696 ms 92100 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

const int maxN = 200000 + 5;
struct Rect {
	int L, D, R, U;
	Rect() {}
	Rect(int l, int d, int r, int u) : L(l), D(d), R(r), U(u) {}
	LL area() const {
		return (LL)max(0, R - L + 1) * (LL)max(0, U - D + 1);
	}
	bool hit(pii p) const {
		return L <= p.first && p.first <= R && D <= p.second && p.second <= U;
	}
};
int nx, ny;
vector<int> tx, ty;

Rect com(Rect x, Rect y) {
	return Rect(max(x.L, y.L), max(x.D, y.D), min(x.R, y.R), min(x.U, y.U));
}

void disc(vector<Rect> &v) {
	{
	vector<int> &t = tx;
	t.clear();
	for(auto r : v) t.push_back(r.L), t.push_back(r.R);
	sort(t.begin(), t.end());
//	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> c(2 * v.size(), 0);
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.L) - t.begin();
		r.L = i + ++c[i];
	}
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.R) - t.begin();
		r.R = i + ++c[i];
	}
	nx = t.size();
	}
	{
	vector<int> &t = ty;
	t.clear();
	for(auto r : v) t.push_back(r.D), t.push_back(r.U);
	sort(t.begin(), t.end());
//	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> c(2 * v.size(), 0);
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.D) - t.begin();
		r.D = i + ++c[i];
	}
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.U) - t.begin();
		r.U = i + ++c[i];
	}
	ny = t.size();
	}
	
	assert(nx == ny);
}

vector<Rect> ans;

vector<int> oned(vector<pii> &v) {
	displayv(v);
	vector<int> res;
	sort(v.begin(), v.end());
	int last = max(nx, ny) + 1;
	for(int i = (int)v.size() - 1; i >= 0; --i) {
		if(v[i].first <= last && last <= v[i].second) continue;
		else res.push_back(last = v[i].first);
	}
	displayv(res);
	return res;
}

struct Segt { // i = L
#define lson (o*2)
#define rson (lson | 1)
	int n;
	Rect ext[maxN * 8];
	Segt() {}
	void clear(int n) {
		this->n = n;
		for(int i = 0; i <= 4 * n; ++i)
			ext[i] = Rect(1, 1, n, n);
	}
	void insert(int o, int L, int R, Rect r) {
		if(L == R) {
			ext[o] = r;
		} else {
			int M = (L + R) >> 1;
			if(r.L <= M) insert(lson, L, M, r);
			else insert(rson, M + 1, R, r);
			ext[o] = com(ext[lson], ext[rson]);
		}
	}
	void erase(int o, int L, int R, Rect r) {
		if(L == R) {
			ext[o] = Rect(1, 1, n, n);
		} else {
			int M = (L + R) >> 1;
			if(r.L <= M) erase(lson, L, M, r);
			else erase(rson, M + 1, R, r);
			ext[o] = com(ext[lson], ext[rson]);
		}
	}
	Rect query(int o, int L, int R, int ql, int qr) {
		if(ql <= L && R <= qr) {
			return ext[o];
		} else {
			int M = (L + R) >> 1;
			Rect r(1, 1, n, n);
			if(ql <= M) r = com(r, query(lson, L, M, ql, qr));
			if(qr > M) r = com(r, query(rson, M + 1, R, ql, qr));
			return r;
		}
	}
#undef lson
#undef rson
} up, down, both;

bool solve(vector<Rect> &v, int k, vector<pii> &res) {
	res.clear();
	{ // k == 0
		if(v.size() == 0) return true;
		if(k <= 0) return false;
	}
	
	Rect c(1, 1, nx, ny);
	for(auto r : v) c = com(c, r);
	{ // k == 1
		if(c.area() > 0) {
			res.emplace_back(c.L, c.D);
			return true;
		}
		if(k <= 1) return false;
	}
	if(c.L <= c.R) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].D, v[i].U);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(c.L, p);
		return true;
	}
	if(c.D <= c.U) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].L, v[i].R);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(p, c.D);
		return true;
	}
	{ // k == 2
		auto check = [&](pii x, pii y) {
			for(auto r : v) {
				if(!r.hit(x) && !r.hit(y)) {
					return false;
				}
			}
			res.push_back(x);
			res.push_back(y);
			return true;
		};
		if(check(pii(c.L, c.D), pii(c.R, c.U))) return true;
		if(check(pii(c.L, c.U), pii(c.R, c.D))) return true;
		if(k <= 2) return false;
	}
	{ // k == 3
		auto check = [&](pii x) {
			vector<Rect> nv;
			vector<pii> sol;
			for(auto r : v) {
				if(!r.hit(x)) nv.push_back(r);
			}
			if(solve(nv, k - 1, sol)) {
				res.push_back(x);
				res.insert(res.end(), sol.begin(), sol.end());
				return true;
			}
			return false;
		};
		if(check(pii(c.L, c.D))) return true;
		if(check(pii(c.L, c.U))) return true;
		if(check(pii(c.R, c.D))) return true;
		if(check(pii(c.R, c.U))) return true;
		if(k <= 3) return false;
	}
	{
		// c.R ~ c.L; c.U ~ c.D
		int L = c.R, R = c.L, D = c.U, U = c.D;
		eprintf("heart %d %d %d %d\n", tx[L - 1], ty[D - 1], tx[R - 1], ty[U - 1]);
		set<int> us, ds;
		vector<pii> es; // (y, i)
		pii llim(1, ny);
		
		auto add = [&](Rect r, int coef) {
			
			assert(coef == 1 || coef == -1);
			Rect CL, CR, CD, CU;
			pii p;
			CL = com(Rect(L, D, L, U), r);
			CR = com(Rect(R, D, R, U), r);
			CD = com(Rect(L, D, R, D), r);
			CU = com(Rect(L, U, R, U), r);
			assert(CL.area() > 0);
			if(CR.area()) {
				if(coef == 1) ds.insert(r.D), us.insert(r.U);
				else ds.erase(r.D), us.erase(r.U);
			} else if(CU.area()) {
				if(coef == 1) up.insert(1, 1, nx, r);
				else up.erase(1, 1, nx, r);
			} else {
				if(coef == 1) down.insert(1, 1, nx, r);
				else down.erase(1, 1, nx, r);
			}
		};
		
		for(int i = 0; i < (int)v.size(); ++i) {
			Rect CL, CR, CD, CU;
			pii p;
			CL = com(Rect(L, D, L, U), v[i]);
			CR = com(Rect(R, D, R, U), v[i]);
			CD = com(Rect(L, D, R, D), v[i]);
			CU = com(Rect(L, U, R, U), v[i]);
//			if(tx[v[i].R - 1] == 556967885) {
//				eprintf("got = %d %d %d %d\n", tx[v[i].L - 1], ty[v[i].D - 1], tx[v[i].R - 1], ty[v[i].U - 1]);
//				eprintf("%lld %lld %lld %lld\n", CL.area(), CR.area(), CD.area(), CU.area());
//			}
			int adj = !!CL.area() + !!CR.area() + !!CD.area() + !!CU.area();
			assert(adj > 0);
			if(adj >= 3) continue;
			if(adj == 1) {
				if(CL.area()) chmax(llim.first, CL.D), chmin(llim.second, CL.U);
				else if(CR.area()) ds.insert(CL.D), us.insert(CL.U);
				else if(CD.area()) down.insert(1, 1, nx, v[i]);
				else if(CU.area()) up.insert(1, 1, nx, v[i]);
			} else {
				if(CL.area()) add(v[i], 1), es.emplace_back(CL.D, -i-1), es.emplace_back(CL.U + 1, i);
				else {
					if(CU.area() && CD.area()) both.insert(1, 1, nx, v[i]);
					else if(CU.area()) up.insert(1, 1, nx, v[i]);
					else if(CD.area()) down.insert(1, 1, nx, v[i]);
				}
			}
		}
//		eprintf("llim = [%d %d]\n", ty[llim.first - 1], ty[llim.second - 1]);
		es.emplace_back(llim.first, maxN);
		es.emplace_back(llim.second, maxN);
		sort(es.begin(), es.end());
		for(int i = 0; i < (int)es.size(); ++i) {
			int id = es[i].second;
			if(id < 0) add(v[-id-1], -1);
			else if(id != maxN) add(v[id], 1);
			else {}
			
			if((i + 1 == (int)es.size() || es[i + 1].first != es[i].first)
				&& llim.first <= es[i].first && es[i].first <= llim.second) {
//				eprintf("L picks %d\n", ty[es[i].first - 1]);
				// case 1: U <= D
				{
					Rect u = com(up.query(1, 1, nx, 1, nx), both.query(1, 1, nx, 1, nx));
					Rect d = down.query(1, 1, nx, 1, nx);
					if(d.R < u.R) goto NEXT;
					if(u.R + 1 <= nx) d = com(d, both.query(1, 1, nx, u.R + 1, nx));
					
					Rect rest(R, D, R, U);
					if(ds.size()) chmax(rest.D, *ds.rbegin());
					if(us.size()) chmin(rest.U, *us.begin());
					if(u.R + 1 <= nx) rest = com(rest, up.query(1, 1, nx, u.R + 1, nx));
					if(d.R + 1 <= ny) rest = com(rest, down.query(1, 1, nx, d.R + 1, nx)), rest = com(rest, both.query(1, 1, nx, d.R + 1, nx));
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
//					eprintf("rest = %d %d %d %d\n", tx[rest.L - 1], ty[rest.D - 1], tx[rest.R - 1], ty[rest.U - 1]);
					if(rest.area() > 0) {
						res.emplace_back(L, es[i].first);
						res.emplace_back(u.R, U);
						res.emplace_back(d.R, D);
						res.emplace_back(rest.L, rest.D);
						return true;
					}
				}
				NEXT:
				// case 2: D <= U
				{
					Rect d = com(down.query(1, 1, nx, 1, nx), both.query(1, 1, nx, 1, nx));
					Rect u = up.query(1, 1, nx, 1, nx);
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
					if(u.R < d.R) continue;
					if(d.R + 1 <= nx) u = com(u, both.query(1, 1, nx, d.R + 1, nx));
					
					Rect rest(R, D, R, U);
					if(ds.size()) chmax(rest.D, *ds.rbegin());
					if(us.size()) chmin(rest.U, *us.begin());
					if(d.R + 1 <= nx) rest = com(rest, down.query(1, 1, nx, d.R + 1, nx));
					if(u.R + 1 <= ny) rest = com(rest, up.query(1, 1, nx, u.R + 1, nx)), rest = com(rest, both.query(1, 1, nx, u.R + 1, nx));
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
//					eprintf("rest = %d %d %d %d\n", tx[rest.L - 1], ty[rest.D - 1], tx[rest.R - 1], ty[rest.U - 1]);
					if(rest.area() > 0) {
						res.emplace_back(L, es[i].first);
						res.emplace_back(d.R, D);
						res.emplace_back(u.R, U);
						res.emplace_back(rest.L, rest.D);
						return true;
					}
				}
			}
		}
		
		if(k <= 4) return false;
	}
	return false;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	int n, k;
	cin >> n >> k;
	vector<Rect> v;
	for(int i = 0; i < n; ++i) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		v.emplace_back(l, d, r, u);
	}
	disc(v);
	for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
	
	down.clear(2 * n);
	up.clear(2 * n);
	both.clear(2 * n);
	
	vector<pii> res;
	bool ok = solve(v, k, res);
	assert(ok);
	while((int)res.size() < k) res.emplace_back(1, 1);
	for(auto p : res) cout << tx[p.first - 1] << " " << ty[p.second - 1] << endl;
	return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:357:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  357 |  for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
      |           ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1204 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1152 KB Output is correct
12 Correct 4 ms 1152 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 5 ms 1184 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 4 ms 1152 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 4 ms 1280 KB Output is correct
15 Correct 3 ms 1152 KB Output is correct
16 Correct 3 ms 1152 KB Output is correct
17 Correct 5 ms 1280 KB Output is correct
18 Correct 4 ms 1152 KB Output is correct
19 Correct 3 ms 1152 KB Output is correct
20 Correct 4 ms 1280 KB Output is correct
21 Correct 3 ms 1152 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 4 ms 1280 KB Output is correct
24 Correct 3 ms 1280 KB Output is correct
25 Correct 4 ms 1280 KB Output is correct
26 Correct 4 ms 1280 KB Output is correct
27 Correct 4 ms 1280 KB Output is correct
28 Correct 3 ms 1280 KB Output is correct
29 Correct 3 ms 1280 KB Output is correct
30 Correct 4 ms 1280 KB Output is correct
31 Correct 4 ms 1280 KB Output is correct
32 Correct 4 ms 1280 KB Output is correct
33 Correct 4 ms 1152 KB Output is correct
34 Correct 4 ms 1280 KB Output is correct
35 Correct 4 ms 1280 KB Output is correct
36 Correct 5 ms 1280 KB Output is correct
37 Correct 4 ms 1280 KB Output is correct
38 Correct 4 ms 1280 KB Output is correct
39 Correct 4 ms 1280 KB Output is correct
40 Correct 4 ms 1280 KB Output is correct
41 Correct 5 ms 1280 KB Output is correct
42 Correct 4 ms 1280 KB Output is correct
43 Correct 4 ms 1280 KB Output is correct
44 Correct 5 ms 1280 KB Output is correct
45 Correct 3 ms 1280 KB Output is correct
46 Correct 4 ms 1280 KB Output is correct
47 Correct 4 ms 1280 KB Output is correct
48 Correct 5 ms 1280 KB Output is correct
49 Correct 5 ms 1280 KB Output is correct
50 Correct 4 ms 1280 KB Output is correct
51 Correct 4 ms 1280 KB Output is correct
52 Correct 4 ms 1280 KB Output is correct
53 Correct 5 ms 1280 KB Output is correct
54 Correct 4 ms 1280 KB Output is correct
55 Correct 4 ms 1280 KB Output is correct
56 Correct 5 ms 1280 KB Output is correct
57 Correct 4 ms 1280 KB Output is correct
58 Correct 4 ms 1280 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 353 ms 83832 KB Output is correct
6 Correct 361 ms 83784 KB Output is correct
7 Correct 362 ms 83808 KB Output is correct
8 Correct 367 ms 83828 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1204 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 373 ms 83872 KB Output is correct
6 Correct 406 ms 83808 KB Output is correct
7 Correct 354 ms 83828 KB Output is correct
8 Correct 391 ms 83936 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 3 ms 1152 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1152 KB Output is correct
12 Correct 4 ms 1152 KB Output is correct
13 Correct 378 ms 85472 KB Output is correct
14 Correct 390 ms 85404 KB Output is correct
15 Correct 386 ms 85344 KB Output is correct
16 Correct 395 ms 85356 KB Output is correct
17 Correct 380 ms 85424 KB Output is correct
18 Correct 393 ms 85348 KB Output is correct
19 Correct 365 ms 87960 KB Output is correct
20 Correct 385 ms 88540 KB Output is correct
21 Correct 383 ms 87904 KB Output is correct
22 Correct 377 ms 88440 KB Output is correct
23 Correct 401 ms 88332 KB Output is correct
24 Correct 384 ms 88036 KB Output is correct

Subtask #8
79.0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 5 ms 1184 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 4 ms 1152 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 4 ms 1280 KB Output is correct
15 Correct 3 ms 1152 KB Output is correct
16 Correct 3 ms 1152 KB Output is correct
17 Correct 5 ms 1280 KB Output is correct
18 Correct 4 ms 1152 KB Output is correct
19 Correct 3 ms 1152 KB Output is correct
20 Correct 4 ms 1280 KB Output is correct
21 Correct 3 ms 1152 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 4 ms 1280 KB Output is correct
24 Correct 3 ms 1280 KB Output is correct
25 Correct 4 ms 1280 KB Output is correct
26 Correct 4 ms 1280 KB Output is correct
27 Correct 4 ms 1280 KB Output is correct
28 Correct 3 ms 1280 KB Output is correct
29 Correct 3 ms 1280 KB Output is correct
30 Correct 4 ms 1280 KB Output is correct
31 Correct 4 ms 1280 KB Output is correct
32 Correct 4 ms 1280 KB Output is correct
33 Correct 4 ms 1152 KB Output is correct
34 Correct 4 ms 1280 KB Output is correct
35 Correct 4 ms 1280 KB Output is correct
36 Correct 5 ms 1280 KB Output is correct
37 Correct 4 ms 1280 KB Output is correct
38 Correct 4 ms 1280 KB Output is correct
39 Correct 4 ms 1280 KB Output is correct
40 Correct 4 ms 1280 KB Output is correct
41 Correct 5 ms 1280 KB Output is correct
42 Correct 4 ms 1280 KB Output is correct
43 Correct 4 ms 1280 KB Output is correct
44 Correct 5 ms 1280 KB Output is correct
45 Correct 3 ms 1280 KB Output is correct
46 Correct 4 ms 1280 KB Output is correct
47 Correct 4 ms 1280 KB Output is correct
48 Correct 5 ms 1280 KB Output is correct
49 Correct 5 ms 1280 KB Output is correct
50 Correct 4 ms 1280 KB Output is correct
51 Correct 4 ms 1280 KB Output is correct
52 Correct 4 ms 1280 KB Output is correct
53 Correct 5 ms 1280 KB Output is correct
54 Correct 4 ms 1280 KB Output is correct
55 Correct 4 ms 1280 KB Output is correct
56 Correct 5 ms 1280 KB Output is correct
57 Correct 4 ms 1280 KB Output is correct
58 Correct 4 ms 1280 KB Output is correct
59 Correct 399 ms 85472 KB Output is correct
60 Correct 385 ms 85508 KB Output is correct
61 Correct 397 ms 85472 KB Output is correct
62 Correct 371 ms 85440 KB Output is correct
63 Correct 390 ms 85452 KB Output is correct
64 Correct 376 ms 85500 KB Output is correct
65 Correct 370 ms 88184 KB Output is correct
66 Correct 394 ms 90284 KB Output is correct
67 Correct 449 ms 88032 KB Output is correct
68 Correct 584 ms 91236 KB Output is correct
69 Correct 643 ms 92000 KB Output is correct
70 Correct 406 ms 90968 KB Output is correct
71 Correct 375 ms 88036 KB Output is correct
72 Correct 667 ms 91540 KB Output is correct
73 Correct 388 ms 87236 KB Output is correct
74 Correct 394 ms 91492 KB Output is correct
75 Correct 505 ms 90432 KB Output is correct
76 Correct 410 ms 91328 KB Output is correct
77 Correct 394 ms 88156 KB Output is correct
78 Correct 591 ms 91432 KB Output is correct
79 Correct 398 ms 87908 KB Output is correct
80 Correct 371 ms 87980 KB Output is correct
81 Correct 556 ms 91032 KB Output is correct
82 Correct 410 ms 90976 KB Output is correct
83 Correct 408 ms 90264 KB Output is correct
84 Correct 416 ms 91580 KB Output is correct
85 Correct 427 ms 91984 KB Output is correct
86 Correct 396 ms 87708 KB Output is correct
87 Correct 405 ms 91860 KB Output is correct
88 Correct 425 ms 91932 KB Output is correct
89 Correct 538 ms 90872 KB Output is correct
90 Correct 550 ms 91392 KB Output is correct
91 Correct 506 ms 90160 KB Output is correct
92 Correct 548 ms 92100 KB Output is correct
93 Correct 532 ms 91588 KB Output is correct
94 Correct 671 ms 91256 KB Output is correct
95 Correct 548 ms 91604 KB Output is correct
96 Correct 578 ms 91360 KB Output is correct
97 Correct 601 ms 91348 KB Output is correct
98 Correct 584 ms 91008 KB Output is correct
99 Correct 528 ms 91496 KB Output is correct
100 Correct 592 ms 91448 KB Output is correct
101 Correct 566 ms 91452 KB Output is correct
102 Correct 467 ms 87712 KB Output is correct
103 Correct 623 ms 91772 KB Output is correct
104 Correct 484 ms 90544 KB Output is correct
105 Correct 610 ms 91756 KB Output is correct
106 Correct 586 ms 91588 KB Output is correct
107 Correct 532 ms 91620 KB Output is correct
108 Correct 573 ms 91716 KB Output is correct
109 Correct 584 ms 91400 KB Output is correct
110 Correct 551 ms 91784 KB Output is correct
111 Correct 563 ms 90660 KB Output is correct
112 Correct 576 ms 91860 KB Output is correct
113 Correct 514 ms 88400 KB Output is correct
114 Correct 500 ms 88448 KB Output is correct
115 Correct 526 ms 88432 KB Output is correct
116 Correct 524 ms 88536 KB Output is correct
117 Correct 616 ms 90640 KB Output is correct
118 Correct 581 ms 90632 KB Output is correct
119 Correct 649 ms 90628 KB Output is correct
120 Correct 618 ms 90640 KB Output is correct
121 Correct 696 ms 90644 KB Output is correct
122 Correct 586 ms 90684 KB Output is correct
123 Correct 591 ms 90664 KB Output is correct
124 Correct 630 ms 90632 KB Output is correct
125 Correct 589 ms 90660 KB Output is correct
126 Correct 592 ms 90732 KB Output is correct