oj.uz

Submission #810337

# Submission time Handle Problem Language Result Execution time Memory
810337 2023-08-06T08:38:04 Z model_code Cell Automaton (JOI23_cell) C++17
100 / 100
 4138 ms 698756 KB 
/*
	FULL-SCORE SOLUTION
	- Time Complexity: O((Q + N) log N)
*/

#include <set>
#include <tuple>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class value {
public:
	long long x; int p1, p2; // value: x + p1 * eps + p2 * eps^2 (eps > 0 is an arbitrary value which is small enough)
	value() : x(0), p1(0), p2(0) {}
	value(long long x_, int p1_, int p2_) : x(x_), p1(p1_), p2(p2_) {}
	bool operator<(const value& v) const { return x != v.x ? x < v.x : (p1 != v.p1 ? p1 < v.p1 : p2 < v.p2); }
	bool operator>(const value& v) const { return x != v.x ? x > v.x : (p1 != v.p1 ? p1 > v.p1 : p2 > v.p2); }
	value operator+() const { return value(+x, +p1, +p2); }
	value operator-() const { return value(-x, -p1, -p2); }
	value& operator+=(const value& v) { x += v.x; p1 += v.p1; p2 += v.p2; return *this; }
	value& operator-=(const value& v) { x -= v.x; p1 -= v.p1; p2 -= v.p2; return *this; }
	value operator+(const value& v) const { return value(*this) += v; }
	value operator-(const value& v) const { return value(*this) -= v; }
};

class nearest_info {
public:
	int idx; value d1, d2;
	nearest_info() : idx(-1), d1(value()), d2(value()) {}
	nearest_info(int idx_, const value& d1_, const value& d2_) : idx(idx_), d1(d1_), d2(d2_) {}
};

class segment {
public:
	long long a, b, l, r; // y = ax + b (l <= x <= r)
	segment() : a(0), b(0), l(0), r(0) {}
	segment(long long a_, long long b_, long long l_, long long r_) : a(a_), b(b_), l(l_), r(r_) {}
};

// FUNCTION FOR SOLVING "CONTINUOUS VERSION" OF THE PROBLEM
// - Given N points (X[0], Y[0]), ..., (X[N-1], Y[N-1]) and Q queries with T[0], T[1], ..., T[Q-1]
// - For each query j, answer the following:
//   - Consider N squares that, for i = 0, 1, ..., N-1, the lower-left point is at (X[i], Y[i]) and the upper-right point is at (X[i]+T[j], Y[i]+T[j]).
//   - Calculate the area of union of these N squares.
vector<long long> area_union(int N, int Q, const vector<long long>& X, const vector<long long>& Y, const vector<long long>& T) {
	// step #1. compute nearest colliding square, for each square's corner
	vector<value> xp(N), yp(N);
	for (int i = 0; i < N; i++) {
		xp[i] = value(X[i], i, 0);
		yp[i] = value(Y[i], 0, i);
	}
	vector<vector<nearest_info> > nearest(8, vector<nearest_info>(N)); // d1: distance, d2: "orthogonal" distance
	for (int i = 0; i < 8; i++) {
		vector<value> xv(N), yv(N);
		for (int j = 0; j < N; j++) {
			switch (i) {
				case 0: xv[j] = +xp[j]; yv[j] = +yp[j]; break;
				case 1: xv[j] = +xp[j]; yv[j] = -yp[j]; break;
				case 2: xv[j] = -yp[j]; yv[j] = +xp[j]; break;
				case 3: xv[j] = -yp[j]; yv[j] = -xp[j]; break;
				case 4: xv[j] = -xp[j]; yv[j] = -yp[j]; break;
				case 5: xv[j] = -xp[j]; yv[j] = +yp[j]; break;
				case 6: xv[j] = +yp[j]; yv[j] = -xp[j]; break;
				case 7: xv[j] = +yp[j]; yv[j] = +xp[j]; break;
			}
		}
		vector<int> perm(N);
		for (int i = 0; i < N; i++) {
			perm[i] = i;
		}
		sort(perm.begin(), perm.end(), [&](int va, int vb) {
			return yv[va] < yv[vb];
		});
		set<value> s;
		for (int j : perm) {
			set<value>::iterator it = s.lower_bound(xv[j] - yv[j]);
			while (it != s.end() && xv[abs(it->p1)] < xv[j]) {
				it = s.erase(it);
			}
			if (it != s.begin()) {
				--it;
				nearest[i][j] = nearest_info(abs(it->p1), xv[j] - xv[abs(it->p1)], yv[j] - yv[abs(it->p1)]);
			}
			s.insert(xv[j] - yv[j]);
		}
	}
	for (int i = 0; i < 8; i += 2) {
		int p = vector<int>({ 7, 2, 1, 4, 3, 6, 5, 0 })[i];
		for (int j = 0; j < N; j++) {
			if (nearest[i][j].idx != -1 && nearest[p][j].idx != -1) {
				if (nearest[i][j].d1 > nearest[p][j].d1) {
					nearest[i][j] = nearest_info();
				}
				else {
					nearest[p][j] = nearest_info();
				}
			}
		}
	}

	// step #2. compute "time lapse" of each square's edge
	vector<vector<vector<nearest_info> > > timelapse(8, vector<vector<nearest_info> >(N)); // d1: time, d2: distance from another corner
	for (int i = 0; i < 8; i++) {
		int p1 = vector<int>({ 7, 2, 1, 4, 3, 6, 5, 0 })[i];
		int p2 = vector<int>({ 4, 5, 6, 7, 0, 1, 2, 3 })[i];
		for (int j = 0; j < N; j++) {
			if (nearest[p1][j].idx != -1) {
				timelapse[i][j].push_back(nearest_info(nearest[p1][j].idx, nearest[p1][j].d1, nearest[p1][j].d1));
			}
			if (nearest[p2][j].idx != -1) {
				timelapse[i][nearest[p2][j].idx].push_back(nearest_info(j, nearest[p2][j].d1, nearest[p2][j].d2));
			}
		}
		for (int j = 0; j < N; j++) {
			sort(timelapse[i][j].begin(), timelapse[i][j].end(), [&](const nearest_info& f1, const nearest_info& f2) {
				return f1.d1 < f2.d1;
			});
		}
	}

	// step #3. find all crashes & rectangular holes
	const long long INF = (3LL << 60);
	vector<vector<value> > eliminate(4, vector<value>(N, value(INF, 0, 0)));
	for (int i = 0; i < 8; i += 2) {
		for (int j = 0; j < N; j++) {
			if (!timelapse[i + 0][j].empty() && !timelapse[i + 1][j].empty()) {
				nearest_info f0 = timelapse[i + 0][j].back();
				nearest_info f1 = timelapse[i + 1][j].back();
				value t = f0.d2 + f1.d2;
				if ((timelapse[(i + 2) % 8][f0.idx].empty() || timelapse[(i + 2) % 8][f0.idx].back().d1 < t) && timelapse[(i + 3) % 8][f0.idx].back().d1 < t) {
					eliminate[((i + 2) % 8) / 2][f0.idx] = min(eliminate[((i + 2) % 8) / 2][f0.idx], t);
				}
				if ((timelapse[(i + 7) % 8][f1.idx].empty() || timelapse[(i + 7) % 8][f1.idx].back().d1 < t) && timelapse[(i + 6) % 8][f1.idx].back().d1 < t) {
					eliminate[((i + 6) % 8) / 2][f1.idx] = min(eliminate[((i + 6) % 8) / 2][f1.idx], t);
				}
				eliminate[i / 2][j] = min(eliminate[i / 2][j], t);
			}
		}
	}

	// step #4. final calculation
	vector<segment> seg;
	for (int i = 0; i < 8; i += 2) {
		for (int j = 0; j < N; j++) {
			seg.push_back(segment(1, 0, 0, eliminate[i / 2][j].x));
			for (int k = 0; k < 2; k++) {
				if (!timelapse[i + k][j].empty()) {
					seg.push_back(segment(-1, timelapse[i + k][j][0].d2.x, timelapse[i + k][j][0].d1.x, eliminate[i / 2][j].x));
					for (int l = 1; l < timelapse[i + k][j].size(); l++) {
						seg.push_back(segment(0, -(timelapse[i + k][j][l - 1].d2 - timelapse[i + k][j][l].d2).x, timelapse[i + k][j][l].d1.x, eliminate[i / 2][j].x));
					}
				}
			}
		}
	}
	vector<long long> tcomp({ 0, INF });
	for (segment s : seg) {
		if ((s.a != 0 || s.b != 0) && s.l != s.r) {
			tcomp.push_back(s.l);
			tcomp.push_back(s.r);
		}
	}
	sort(tcomp.begin(), tcomp.end());
	tcomp.erase(unique(tcomp.begin(), tcomp.end()), tcomp.end());
	vector<long long> polya(tcomp.size()), polyb(tcomp.size()); // y = ax + b
	for (segment s : seg) {
		if ((s.a != 0 || s.b != 0) && s.l != s.r) {
			int pl = lower_bound(tcomp.begin(), tcomp.end(), s.l) - tcomp.begin();
			int pr = lower_bound(tcomp.begin(), tcomp.end(), s.r) - tcomp.begin();
			polya[pl] += s.a;
			polya[pr] -= s.a;
			polyb[pl] += s.b;
			polyb[pr] -= s.b;
		}
	}
	for (int i = 1; i < tcomp.size(); i++) {
		polya[i] += polya[i - 1];
		polyb[i] += polyb[i - 1];
	}
	vector<long long> cum(tcomp.size());
	for (int i = 0; i < int(tcomp.size()) - 1; i++) {
		long long yl = polya[i] * tcomp[i] + polyb[i];
		long long yr = polya[i] * tcomp[i + 1] + polyb[i];
		cum[i + 1] = cum[i] + (yl + yr) * (tcomp[i + 1] - tcomp[i]) / 4;
	}
	vector<long long> answer(Q);
	for (int i = 0; i < Q; i++) {
		int pos = lower_bound(tcomp.begin(), tcomp.end(), T[i] + 1) - tcomp.begin() - 1;
		long long yl = polya[pos] * tcomp[pos] + polyb[pos];
		long long yt = polya[pos] * T[i] + polyb[pos];
		answer[i] = cum[pos] + (yl + yt) * (T[i] - tcomp[pos]) / 4;
	}
	return answer;
}

// FUNCTION FOR SOLVING THE MAIN PROBLEM
vector<long long> solve(int N, int Q, const vector<long long>& X, const vector<long long>& Y, const vector<long long>& T) {
	auto half = [&](long long x) {
		return (x >= 0 ? x / 2 : -((-x + 1) / 2));
	};
	vector<long long> xa, ya, xb, yb;
	for (int i = 0; i < N; i++) {
		if ((X[i] + Y[i]) % 2 == 0) {
			xa.push_back((X[i] + Y[i] + 0) / 2); ya.push_back((X[i] - Y[i] + 0) / 2);
			xa.push_back((X[i] + Y[i] + 0) / 2); ya.push_back((X[i] - Y[i] + 2) / 2);
			xa.push_back((X[i] + Y[i] + 2) / 2); ya.push_back((X[i] - Y[i] + 0) / 2);
			xa.push_back((X[i] + Y[i] + 2) / 2); ya.push_back((X[i] - Y[i] + 2) / 2);
			xb.push_back((X[i] + Y[i] + 2) / 2); yb.push_back((X[i] - Y[i] + 2) / 2);
		}
		else {
			xa.push_back((X[i] + Y[i] + 1) / 2); ya.push_back((X[i] - Y[i] + 1) / 2);
			xb.push_back((X[i] + Y[i] + 1) / 2); yb.push_back((X[i] - Y[i] + 1) / 2);
			xb.push_back((X[i] + Y[i] + 1) / 2); yb.push_back((X[i] - Y[i] + 3) / 2);
			xb.push_back((X[i] + Y[i] + 3) / 2); yb.push_back((X[i] - Y[i] + 1) / 2);
			xb.push_back((X[i] + Y[i] + 3) / 2); yb.push_back((X[i] - Y[i] + 3) / 2);
		}
	}
	vector<long long> T2(Q * 2);
	for (int i = 0; i < Q; i++) {
		T2[i * 2 + 0] = T[i];
		T2[i * 2 + 1] = (T[i] >= 1 ? T[i] - 1 : 0);
	}
	vector<long long> resa = area_union(xa.size(), Q * 2, xa, ya, T2);
	vector<long long> resb = area_union(xb.size(), Q * 2, xb, yb, T2);
	vector<long long> answer(Q, 0);
	for (int i = 0; i < Q; i++) {
		if (T[i] == 0) {
			answer[i] = N;
		}
		else {
			answer[i] += resa[2 * i + 0] - (T[i] >= 2 ? resa[2 * i + 1] : 0);
			answer[i] += resb[2 * i + 0] - (T[i] >= 2 ? resb[2 * i + 1] : 0);
			if (T[i] == 1) {
				answer[i] -= N;
			}
		}
	}
	return answer;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q;
	vector<long long> X(N), Y(N), T(Q);
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> T[i];
	}
	vector<long long> answer = solve(N, Q, X, Y, T);
	for (int i = 0; i < Q; i++) {
		cout << answer[i] << '\n';
	}
	return 0;
}

Compilation message

cell.cpp: In function 'std::vector<long long int> area_union(int, int, const std::vector<long long int>&, const std::vector<long long int>&, const std::vector<long long int>&)':
cell.cpp:151:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nearest_info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |      for (int l = 1; l < timelapse[i + k][j].size(); l++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.cpp:178:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  for (int i = 1; i < tcomp.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
cell.cpp: In function 'std::vector<long long int> solve(int, int, const std::vector<long long int>&, const std::vector<long long int>&, const std::vector<long long int>&)':
cell.cpp:200:7: warning: variable 'half' set but not used [-Wunused-but-set-variable]
  200 |  auto half = [&](long long x) {
      |       ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 217 ms 51724 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 20 ms 4736 KB Output is correct
13 Correct 20 ms 4764 KB Output is correct
14 Correct 19 ms 4752 KB Output is correct
15 Correct 19 ms 4820 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 217 ms 51724 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 20 ms 4736 KB Output is correct
13 Correct 20 ms 4764 KB Output is correct
14 Correct 19 ms 4752 KB Output is correct
15 Correct 19 ms 4820 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 776 KB Output is correct
31 Correct 8 ms 2364 KB Output is correct
32 Correct 3079 ms 418920 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 2 ms 1108 KB Output is correct
35 Correct 17 ms 6788 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 21 ms 4940 KB Output is correct
39 Correct 247 ms 51596 KB Output is correct
40 Correct 3077 ms 419068 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3324 ms 687032 KB Output is correct
2 Correct 3543 ms 686956 KB Output is correct
3 Correct 3410 ms 686928 KB Output is correct
4 Correct 3493 ms 686976 KB Output is correct
5 Correct 3369 ms 687056 KB Output is correct
6 Correct 3410 ms 687028 KB Output is correct
7 Correct 3383 ms 687036 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 22 ms 7496 KB Output is correct
11 Correct 3387 ms 686900 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3324 ms 687032 KB Output is correct
2 Correct 3543 ms 686956 KB Output is correct
3 Correct 3410 ms 686928 KB Output is correct
4 Correct 3493 ms 686976 KB Output is correct
5 Correct 3369 ms 687056 KB Output is correct
6 Correct 3410 ms 687028 KB Output is correct
7 Correct 3383 ms 687036 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 22 ms 7496 KB Output is correct
11 Correct 3387 ms 686900 KB Output is correct
12 Correct 3461 ms 698756 KB Output is correct
13 Correct 3421 ms 698660 KB Output is correct
14 Correct 3510 ms 698748 KB Output is correct
15 Correct 3464 ms 698700 KB Output is correct
16 Correct 81 ms 31564 KB Output is correct
17 Correct 90 ms 31564 KB Output is correct
18 Correct 102 ms 32128 KB Output is correct
19 Correct 3561 ms 698740 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9000 KB Output is correct
2 Correct 36 ms 9048 KB Output is correct
3 Correct 51 ms 9320 KB Output is correct
4 Correct 65 ms 9280 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9000 KB Output is correct
2 Correct 36 ms 9048 KB Output is correct
3 Correct 51 ms 9320 KB Output is correct
4 Correct 65 ms 9280 KB Output is correct
5 Correct 150 ms 36764 KB Output is correct
6 Correct 152 ms 36752 KB Output is correct
7 Correct 157 ms 36840 KB Output is correct
8 Correct 147 ms 36916 KB Output is correct
9 Correct 164 ms 36940 KB Output is correct
10 Correct 152 ms 36888 KB Output is correct
11 Correct 170 ms 36852 KB Output is correct
12 Correct 159 ms 36840 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 217 ms 51724 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 20 ms 4736 KB Output is correct
13 Correct 20 ms 4764 KB Output is correct
14 Correct 19 ms 4752 KB Output is correct
15 Correct 19 ms 4820 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 776 KB Output is correct
31 Correct 8 ms 2364 KB Output is correct
32 Correct 3079 ms 418920 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 2 ms 1108 KB Output is correct
35 Correct 17 ms 6788 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 21 ms 4940 KB Output is correct
39 Correct 247 ms 51596 KB Output is correct
40 Correct 3077 ms 419068 KB Output is correct
41 Correct 3324 ms 687032 KB Output is correct
42 Correct 3543 ms 686956 KB Output is correct
43 Correct 3410 ms 686928 KB Output is correct
44 Correct 3493 ms 686976 KB Output is correct
45 Correct 3369 ms 687056 KB Output is correct
46 Correct 3410 ms 687028 KB Output is correct
47 Correct 3383 ms 687036 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 22 ms 7496 KB Output is correct
51 Correct 3387 ms 686900 KB Output is correct
52 Correct 3461 ms 698756 KB Output is correct
53 Correct 3421 ms 698660 KB Output is correct
54 Correct 3510 ms 698748 KB Output is correct
55 Correct 3464 ms 698700 KB Output is correct
56 Correct 81 ms 31564 KB Output is correct
57 Correct 90 ms 31564 KB Output is correct
58 Correct 102 ms 32128 KB Output is correct
59 Correct 3561 ms 698740 KB Output is correct
60 Correct 36 ms 9000 KB Output is correct
61 Correct 36 ms 9048 KB Output is correct
62 Correct 51 ms 9320 KB Output is correct
63 Correct 65 ms 9280 KB Output is correct
64 Correct 150 ms 36764 KB Output is correct
65 Correct 152 ms 36752 KB Output is correct
66 Correct 157 ms 36840 KB Output is correct
67 Correct 147 ms 36916 KB Output is correct
68 Correct 164 ms 36940 KB Output is correct
69 Correct 152 ms 36888 KB Output is correct
70 Correct 170 ms 36852 KB Output is correct
71 Correct 159 ms 36840 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 0 ms 340 KB Output is correct
74 Correct 0 ms 340 KB Output is correct
75 Correct 2697 ms 429648 KB Output is correct
76 Correct 2767 ms 429228 KB Output is correct
77 Correct 2737 ms 429212 KB Output is correct
78 Correct 2727 ms 429172 KB Output is correct
79 Correct 3371 ms 439060 KB Output is correct
80 Correct 3468 ms 466652 KB Output is correct
81 Correct 3558 ms 467792 KB Output is correct
82 Correct 3705 ms 467784 KB Output is correct
83 Correct 4138 ms 467804 KB Output is correct
84 Correct 3972 ms 468692 KB Output is correct