Submission #161300

# Submission time Handle Problem Language Result Execution time Memory
161300 2019-11-01T18:36:50 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
3920 ms 34944 KB
#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
 
typedef int ll;
 
typedef long double ld;
 
using namespace std;
 
const ll inf = 2e9 + 500;
const ll maxn = 2e5 + 100;
const ll block = 150;
const ll block_sz = 2000;
 
ll n, m, k, t;
 
struct seg{
	ll l;
	ll r;
	inline ll sz() const {
		return r - l + 1;
	}
	ll i;
};
 
inline bool operator==(seg a, seg b) {
	return a.i == b.i;
}
 
vector <seg> S;
 
struct R {
	bool operator()(seg a, seg b) const {
		if (a.r == b.r) {
			return a.i < b.i;
		}
		return a.r < b.r; 
	}
};
 
struct L {
	bool operator()(seg a, seg b) const {
		if (a.l == b.l) {
			return a.i < b.i;
		}
		return a.l < b.l;
	}
};
 
vector <seg> lasts;
 
inline bool cmp(seg a, seg b) {
	return (a.r - a.l) < (b.r - b.l);
}
 
inline bool cmpl(const seg& a, const seg& b) {
	return a.l < b.l;
}
 
inline bool cmpr(const seg& a, const seg& b) {
	return a.r < b.r;
}
 
inline bool cmpsz(const seg& a, const seg& b) {
	return a.sz() < b.sz();
}
 
vector <seg> segs;
 
vector <seg> R[block];
 
vector <seg> L[block];
 
ll MNL[block];
ll MXL[block];
ll MNR[block];
ll MXR[block];
 
ll IL[maxn];
ll IR[maxn];
 
bool used[maxn];
 
inline void buildL(ll q) {
	ll w;
	sort(L[q].begin(), L[q].end(), cmpsz);
	MNL[q] = inf;
	MXL[q] = -inf;
	for (w = 0; w < L[q].size(); w++) {
		MNL[q] = min(MNL[q], L[q][w].l);
		MXL[q] = max(MXL[q], L[q][w].l);
	}
}
 
inline void buildR(ll q) {
	ll w;
 	MNR[q] = inf;
	MXR[q] = -inf;
	sort(R[q].begin(), R[q].end(), cmpsz);
	for (w = 0; w < R[q].size(); w++) {
		MNR[q] = min(MNR[q], R[q][w].r);
		MXR[q] = max(MXR[q], R[q][w].r);
	}
}
 
inline void rebuild() { 
	ll q, w;
	lasts.clear();
	ll blocki = 0;
	for (q = 0; q < block; q++) {
		R[q].clear();
		L[q].clear();
	}
	sort(segs.begin(), segs.end(), cmpl);
	for (auto p : segs) {
		if (used[p.i]) {
			continue;
		}
		if (L[blocki].size() > block_sz) {
			blocki++;
		}
		IL[p.i] = blocki;
		L[blocki].pb(p);
	}
	sort(segs.begin(), segs.end(), cmpr);
	for (auto p: segs) {
		if (used[p.i]) {
			continue;
		}
		if (R[blocki].size() > block_sz) {
			blocki++;
		}
		IR[p.i] = blocki;
		R[blocki].pb(p);
	}
	for (q = 0; q < block; q++) {
		buildL(q);
	}
	for (q = 0; q < block; q++) {
		buildR(q);
	}
}
 
inline void add(seg a) {
	lasts.pb(a);
	S.pb(a);
	segs.push_back(a);
	IL[a.i] = IR[a.i] = -1;
}
 
inline void del(seg b) { 
	ll il = IL[b.i], ir = IR[b.i];
	if (used[b.i]) {
		return;
	}
	used[b.i] = 1;
	if (il == -1) {
		return;
	}
	L[il].erase(find(L[il].begin(), L[il].end(), b));
	R[ir].erase(find(R[ir].begin(), R[ir].end(), b));
	buildL(il);
	buildR(ir);
}
 
inline ll slowL(ll i, ll x, ll l) {
	ll q;
	ll ans = 0;
	for (q = 0; q < L[i].size(); q++) {
		if (L[i][q].l >= l && L[i][q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}
 
inline ll slowR(ll i, ll x, ll r) {
	ll q;
	ll ans = 0;
	for (q = 0; q < R[i].size(); q++) {
		if (R[i][q].r <= r && R[i][q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}
 
inline ll fastL(ll i, ll x) {
	if (L[i].empty()) {
		return 0;
	}
	seg good;
	good.l = 0; good.r = x - 1; 
	ll j = (lower_bound(L[i].begin(), L[i].end(), good, cmpsz) - L[i].begin());
	return L[i].size() - j;
}
 
inline ll fastR(ll i, ll x) {
	if (R[i].empty()) {
		return 0;
	}
	seg good;
	good.l = 0; good.r = x - 1;
	ll j = (lower_bound(R[i].begin(), R[i].end(), good, cmpsz) - R[i].begin());
	return R[i].size() - j;
}
 
inline ll getansL(ll x, ll l) {
	ll q;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		if (MNL[q] == inf) {
			continue;
		}
		if (MNL[q] >= l) {
			ans += fastL(q, x);
			continue;
		}
		if (MXL[q] < l) {
			continue;
		}
		if (MNL[q] < l) {
			ans += slowL(q, x, l);
		}
	}
 
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q].i]) {
			continue;
		}
		if (lasts[q].l >= l && lasts[q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}
 
inline ll getansR(ll x, ll r) {
	ll q;
	ll ans = 0;
	ll cnt = 0;
	for (q = 0; q < block; q++) {
		if (MNR[q] == inf) {
			continue;
		}
		// if (q > 1) {
		// 	if (MXR[q - 1] > MNR[q]) {
		// 		exit(-1);
		// 	}
		// }
		if (MXR[q] <= r) {
			ll dans = fastR(q, x);
			ans += dans;
			continue;
		}
		if (MNR[q] > r) {
			continue;
		}
		/// MXR[q] > r && MNR[q] <= r, 
		ll dans = slowR(q, x, r);
		ans += dans;
		cnt++;
	}
	// if (cnt > 5) {
	// 	exit(-1);
	// }
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q].i]) {
			continue;
		}
		if (lasts[q].r <= r && lasts[q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}
 
inline ll answer(seg c, ll k) {
	if (c.sz() < k) {
		return 0;
	}
	ll q, w;
	ll ans = 0;
	ll lk = c.r - k + 2, rk = c.l + k - 2;
	ll allans = getansR(k, inf);
	ll dansl = getansL(k, lk);
	ll dansr = getansR(k, rk);
	ans = allans - dansr - dansl;
	return ans;
}
 
signed main() {
	ll q, w, e, a, b, c;
	pyshnapyshnakaa;
	cin >> n >> t;
	// cout << block_sz * block << endl;
	ll nxt = 0;
	ll lastans = 0;
	ll cnt3 = 0;
	for (q = 0; q < block; q++) {
		L[q].reserve(block_sz);
		R[q].reserve(block_sz);
	}
	for (q = 0; q < n; q++) {
		ll comm;
		cin >> comm;
		ll l, r;
		seg x;
		if (comm == 1) {
			cin >> l >> r;
			l ^= (lastans * t);
			r ^= (lastans * t);
			if (l > r) {
				swap(l, r);
			}
			x.l = l; x.r = r;
			x.i = S.size();
			add(x);
		}
		if (comm == 2) {
			cin >> a;
			a--;
			del(S[a]);
		}
		// if (cnt3 > 8e4 && n > 1e5) {
		// 	exit(-1);
		// }
		if (comm == 3) {
			cnt3++;
			cin >> l >> r;
			l ^= (lastans * t);
			r ^= (lastans * t);
			if (lasts.size() >= block_sz) {
				rebuild();
			}
			if (l > r) {
				swap(l, r);
			} 
			x.l = l; x.r = r;
			cin >> c;
			lastans = answer(x, c);
			cout << lastans << '\n';
		}
	}
	return 0;
}

Compilation message

segments.cpp:7:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
segments.cpp: In function 'void buildL(ll)':
segments.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < L[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void buildR(ll)':
segments.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < R[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:115:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < L[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll slowR(ll, ll, ll)':
segments.cpp:188:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < R[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll getansL(ll, ll)':
segments.cpp:235:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll getansR(ll, ll)':
segments.cpp:275:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll answer(seg, ll)':
segments.cpp:290:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:290:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:301:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:301:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:301:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
segments.cpp:305:5: warning: unused variable 'nxt' [-Wunused-variable]
  ll nxt = 0;
     ^~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1532 KB Output is correct
3 Correct 11 ms 1656 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 19 ms 2040 KB Output is correct
6 Correct 24 ms 2040 KB Output is correct
7 Correct 38 ms 1784 KB Output is correct
8 Correct 77 ms 1912 KB Output is correct
9 Correct 87 ms 1916 KB Output is correct
10 Correct 37 ms 2040 KB Output is correct
11 Correct 42 ms 1784 KB Output is correct
12 Correct 38 ms 1924 KB Output is correct
13 Correct 40 ms 2168 KB Output is correct
14 Correct 96 ms 1784 KB Output is correct
15 Correct 11 ms 1656 KB Output is correct
16 Correct 14 ms 1656 KB Output is correct
17 Correct 51 ms 1784 KB Output is correct
18 Correct 64 ms 1988 KB Output is correct
19 Correct 57 ms 1836 KB Output is correct
20 Correct 61 ms 1852 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1164 ms 6768 KB Output is correct
2 Correct 1142 ms 6504 KB Output is correct
3 Correct 1147 ms 6560 KB Output is correct
4 Correct 1063 ms 6900 KB Output is correct
5 Correct 244 ms 10268 KB Output is correct
6 Correct 179 ms 10680 KB Output is correct
7 Correct 1148 ms 6532 KB Output is correct
8 Correct 1148 ms 6688 KB Output is correct
9 Correct 1156 ms 6792 KB Output is correct
10 Correct 1463 ms 3904 KB Output is correct
11 Correct 1474 ms 4768 KB Output is correct
12 Correct 797 ms 8228 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 285 ms 3648 KB Output is correct
2 Correct 261 ms 3508 KB Output is correct
3 Correct 361 ms 3512 KB Output is correct
4 Correct 307 ms 3564 KB Output is correct
5 Correct 563 ms 8204 KB Output is correct
6 Correct 730 ms 7408 KB Output is correct
7 Correct 674 ms 7836 KB Output is correct
8 Correct 191 ms 10256 KB Output is correct
9 Correct 736 ms 10184 KB Output is correct
10 Correct 2338 ms 8476 KB Output is correct
11 Correct 1826 ms 3792 KB Output is correct
12 Correct 2161 ms 8340 KB Output is correct
13 Correct 2633 ms 8144 KB Output is correct
14 Correct 3496 ms 5404 KB Output is correct
15 Correct 3920 ms 5572 KB Output is correct
16 Correct 3395 ms 5000 KB Output is correct
17 Correct 897 ms 7192 KB Output is correct
18 Correct 898 ms 7072 KB Output is correct
19 Correct 920 ms 7192 KB Output is correct
20 Correct 900 ms 7256 KB Output is correct
21 Correct 2216 ms 4340 KB Output is correct
22 Correct 3517 ms 6540 KB Output is correct
23 Correct 3149 ms 8276 KB Output is correct
24 Correct 3526 ms 6728 KB Output is correct
25 Correct 303 ms 4276 KB Output is correct
26 Correct 272 ms 4220 KB Output is correct
27 Correct 292 ms 4084 KB Output is correct
28 Correct 285 ms 4076 KB Output is correct
29 Correct 2850 ms 8376 KB Output is correct
30 Correct 2908 ms 8368 KB Output is correct
31 Correct 698 ms 10768 KB Output is correct
32 Correct 2252 ms 8856 KB Output is correct
33 Correct 2508 ms 8380 KB Output is correct
34 Correct 3495 ms 5404 KB Output is correct
35 Correct 3242 ms 7452 KB Output is correct
36 Correct 2418 ms 8876 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 274 ms 3564 KB Output is correct
2 Correct 259 ms 3644 KB Output is correct
3 Correct 265 ms 3564 KB Output is correct
4 Correct 291 ms 3768 KB Output is correct
5 Correct 647 ms 8740 KB Output is correct
6 Correct 1782 ms 3352 KB Output is correct
7 Correct 513 ms 9360 KB Output is correct
8 Correct 1467 ms 4008 KB Output is correct
9 Correct 3667 ms 5820 KB Output is correct
10 Correct 1977 ms 9124 KB Output is correct
11 Correct 3282 ms 4504 KB Output is correct
12 Correct 401 ms 11156 KB Output is correct
13 Correct 2735 ms 8900 KB Output is correct
14 Correct 3639 ms 6136 KB Output is correct
15 Correct 809 ms 10764 KB Output is correct
16 Correct 2493 ms 8732 KB Output is correct
17 Correct 1161 ms 7132 KB Output is correct
18 Correct 1143 ms 7412 KB Output is correct
19 Correct 1152 ms 7192 KB Output is correct
20 Correct 1137 ms 7204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1532 KB Output is correct
3 Correct 11 ms 1656 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 19 ms 2040 KB Output is correct
6 Correct 24 ms 2040 KB Output is correct
7 Correct 38 ms 1784 KB Output is correct
8 Correct 77 ms 1912 KB Output is correct
9 Correct 87 ms 1916 KB Output is correct
10 Correct 37 ms 2040 KB Output is correct
11 Correct 42 ms 1784 KB Output is correct
12 Correct 38 ms 1924 KB Output is correct
13 Correct 40 ms 2168 KB Output is correct
14 Correct 96 ms 1784 KB Output is correct
15 Correct 11 ms 1656 KB Output is correct
16 Correct 14 ms 1656 KB Output is correct
17 Correct 51 ms 1784 KB Output is correct
18 Correct 64 ms 1988 KB Output is correct
19 Correct 57 ms 1836 KB Output is correct
20 Correct 61 ms 1852 KB Output is correct
21 Correct 1164 ms 6768 KB Output is correct
22 Correct 1142 ms 6504 KB Output is correct
23 Correct 1147 ms 6560 KB Output is correct
24 Correct 1063 ms 6900 KB Output is correct
25 Correct 244 ms 10268 KB Output is correct
26 Correct 179 ms 10680 KB Output is correct
27 Correct 1148 ms 6532 KB Output is correct
28 Correct 1148 ms 6688 KB Output is correct
29 Correct 1156 ms 6792 KB Output is correct
30 Correct 1463 ms 3904 KB Output is correct
31 Correct 1474 ms 4768 KB Output is correct
32 Correct 797 ms 8228 KB Output is correct
33 Correct 274 ms 3564 KB Output is correct
34 Correct 259 ms 3644 KB Output is correct
35 Correct 265 ms 3564 KB Output is correct
36 Correct 291 ms 3768 KB Output is correct
37 Correct 647 ms 8740 KB Output is correct
38 Correct 1782 ms 3352 KB Output is correct
39 Correct 513 ms 9360 KB Output is correct
40 Correct 1467 ms 4008 KB Output is correct
41 Correct 3667 ms 5820 KB Output is correct
42 Correct 1977 ms 9124 KB Output is correct
43 Correct 3282 ms 4504 KB Output is correct
44 Correct 401 ms 11156 KB Output is correct
45 Correct 2735 ms 8900 KB Output is correct
46 Correct 3639 ms 6136 KB Output is correct
47 Correct 809 ms 10764 KB Output is correct
48 Correct 2493 ms 8732 KB Output is correct
49 Correct 1161 ms 7132 KB Output is correct
50 Correct 1143 ms 7412 KB Output is correct
51 Correct 1152 ms 7192 KB Output is correct
52 Correct 1137 ms 7204 KB Output is correct
53 Correct 283 ms 4160 KB Output is correct
54 Correct 283 ms 4148 KB Output is correct
55 Correct 257 ms 4084 KB Output is correct
56 Correct 270 ms 4100 KB Output is correct
57 Correct 1373 ms 5696 KB Output is correct
58 Correct 1471 ms 3616 KB Output is correct
59 Correct 968 ms 7860 KB Output is correct
60 Correct 1441 ms 3224 KB Output is correct
61 Correct 2753 ms 8372 KB Output is correct
62 Correct 1049 ms 10056 KB Output is correct
63 Correct 614 ms 10512 KB Output is correct
64 Correct 1029 ms 10384 KB Output is correct
65 Correct 3546 ms 4852 KB Output is correct
66 Correct 3470 ms 4508 KB Output is correct
67 Correct 2420 ms 8740 KB Output is correct
68 Correct 3150 ms 6944 KB Output is correct
69 Correct 1145 ms 6852 KB Output is correct
70 Correct 1168 ms 6688 KB Output is correct
71 Correct 1158 ms 6964 KB Output is correct
72 Correct 1171 ms 6684 KB Output is correct
73 Correct 3642 ms 5280 KB Output is correct
74 Correct 3245 ms 7036 KB Output is correct
75 Correct 235 ms 10928 KB Output is correct
76 Correct 571 ms 10640 KB Output is correct
77 Correct 277 ms 3764 KB Output is correct
78 Correct 275 ms 3764 KB Output is correct
79 Correct 290 ms 3888 KB Output is correct
80 Correct 272 ms 3764 KB Output is correct
81 Correct 3365 ms 6816 KB Output is correct
82 Correct 3681 ms 5036 KB Output is correct
83 Correct 3313 ms 4344 KB Output is correct
84 Correct 3337 ms 6944 KB Output is correct
85 Correct 2418 ms 8568 KB Output is correct
86 Correct 2247 ms 8476 KB Output is correct
87 Correct 3548 ms 6092 KB Output is correct
88 Correct 3296 ms 4388 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1532 KB Output is correct
3 Correct 11 ms 1656 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 19 ms 2040 KB Output is correct
6 Correct 24 ms 2040 KB Output is correct
7 Correct 38 ms 1784 KB Output is correct
8 Correct 77 ms 1912 KB Output is correct
9 Correct 87 ms 1916 KB Output is correct
10 Correct 37 ms 2040 KB Output is correct
11 Correct 42 ms 1784 KB Output is correct
12 Correct 38 ms 1924 KB Output is correct
13 Correct 40 ms 2168 KB Output is correct
14 Correct 96 ms 1784 KB Output is correct
15 Correct 11 ms 1656 KB Output is correct
16 Correct 14 ms 1656 KB Output is correct
17 Correct 51 ms 1784 KB Output is correct
18 Correct 64 ms 1988 KB Output is correct
19 Correct 57 ms 1836 KB Output is correct
20 Correct 61 ms 1852 KB Output is correct
21 Correct 1164 ms 6768 KB Output is correct
22 Correct 1142 ms 6504 KB Output is correct
23 Correct 1147 ms 6560 KB Output is correct
24 Correct 1063 ms 6900 KB Output is correct
25 Correct 244 ms 10268 KB Output is correct
26 Correct 179 ms 10680 KB Output is correct
27 Correct 1148 ms 6532 KB Output is correct
28 Correct 1148 ms 6688 KB Output is correct
29 Correct 1156 ms 6792 KB Output is correct
30 Correct 1463 ms 3904 KB Output is correct
31 Correct 1474 ms 4768 KB Output is correct
32 Correct 797 ms 8228 KB Output is correct
33 Correct 285 ms 3648 KB Output is correct
34 Correct 261 ms 3508 KB Output is correct
35 Correct 361 ms 3512 KB Output is correct
36 Correct 307 ms 3564 KB Output is correct
37 Correct 563 ms 8204 KB Output is correct
38 Correct 730 ms 7408 KB Output is correct
39 Correct 674 ms 7836 KB Output is correct
40 Correct 191 ms 10256 KB Output is correct
41 Correct 736 ms 10184 KB Output is correct
42 Correct 2338 ms 8476 KB Output is correct
43 Correct 1826 ms 3792 KB Output is correct
44 Correct 2161 ms 8340 KB Output is correct
45 Correct 2633 ms 8144 KB Output is correct
46 Correct 3496 ms 5404 KB Output is correct
47 Correct 3920 ms 5572 KB Output is correct
48 Correct 3395 ms 5000 KB Output is correct
49 Correct 897 ms 7192 KB Output is correct
50 Correct 898 ms 7072 KB Output is correct
51 Correct 920 ms 7192 KB Output is correct
52 Correct 900 ms 7256 KB Output is correct
53 Correct 2216 ms 4340 KB Output is correct
54 Correct 3517 ms 6540 KB Output is correct
55 Correct 3149 ms 8276 KB Output is correct
56 Correct 3526 ms 6728 KB Output is correct
57 Correct 303 ms 4276 KB Output is correct
58 Correct 272 ms 4220 KB Output is correct
59 Correct 292 ms 4084 KB Output is correct
60 Correct 285 ms 4076 KB Output is correct
61 Correct 2850 ms 8376 KB Output is correct
62 Correct 2908 ms 8368 KB Output is correct
63 Correct 698 ms 10768 KB Output is correct
64 Correct 2252 ms 8856 KB Output is correct
65 Correct 2508 ms 8380 KB Output is correct
66 Correct 3495 ms 5404 KB Output is correct
67 Correct 3242 ms 7452 KB Output is correct
68 Correct 2418 ms 8876 KB Output is correct
69 Correct 274 ms 3564 KB Output is correct
70 Correct 259 ms 3644 KB Output is correct
71 Correct 265 ms 3564 KB Output is correct
72 Correct 291 ms 3768 KB Output is correct
73 Correct 647 ms 8740 KB Output is correct
74 Correct 1782 ms 3352 KB Output is correct
75 Correct 513 ms 9360 KB Output is correct
76 Correct 1467 ms 4008 KB Output is correct
77 Correct 3667 ms 5820 KB Output is correct
78 Correct 1977 ms 9124 KB Output is correct
79 Correct 3282 ms 4504 KB Output is correct
80 Correct 401 ms 11156 KB Output is correct
81 Correct 2735 ms 8900 KB Output is correct
82 Correct 3639 ms 6136 KB Output is correct
83 Correct 809 ms 10764 KB Output is correct
84 Correct 2493 ms 8732 KB Output is correct
85 Correct 1161 ms 7132 KB Output is correct
86 Correct 1143 ms 7412 KB Output is correct
87 Correct 1152 ms 7192 KB Output is correct
88 Correct 1137 ms 7204 KB Output is correct
89 Correct 283 ms 4160 KB Output is correct
90 Correct 283 ms 4148 KB Output is correct
91 Correct 257 ms 4084 KB Output is correct
92 Correct 270 ms 4100 KB Output is correct
93 Correct 1373 ms 5696 KB Output is correct
94 Correct 1471 ms 3616 KB Output is correct
95 Correct 968 ms 7860 KB Output is correct
96 Correct 1441 ms 3224 KB Output is correct
97 Correct 2753 ms 8372 KB Output is correct
98 Correct 1049 ms 10056 KB Output is correct
99 Correct 614 ms 10512 KB Output is correct
100 Correct 1029 ms 10384 KB Output is correct
101 Correct 3546 ms 4852 KB Output is correct
102 Correct 3470 ms 4508 KB Output is correct
103 Correct 2420 ms 8740 KB Output is correct
104 Correct 3150 ms 6944 KB Output is correct
105 Correct 1145 ms 6852 KB Output is correct
106 Correct 1168 ms 6688 KB Output is correct
107 Correct 1158 ms 6964 KB Output is correct
108 Correct 1171 ms 6684 KB Output is correct
109 Correct 3642 ms 5280 KB Output is correct
110 Correct 3245 ms 7036 KB Output is correct
111 Correct 235 ms 10928 KB Output is correct
112 Correct 571 ms 10640 KB Output is correct
113 Correct 277 ms 3764 KB Output is correct
114 Correct 275 ms 3764 KB Output is correct
115 Correct 290 ms 3888 KB Output is correct
116 Correct 272 ms 3764 KB Output is correct
117 Correct 3365 ms 6816 KB Output is correct
118 Correct 3681 ms 5036 KB Output is correct
119 Correct 3313 ms 4344 KB Output is correct
120 Correct 3337 ms 6944 KB Output is correct
121 Correct 2418 ms 8568 KB Output is correct
122 Correct 2247 ms 8476 KB Output is correct
123 Correct 3548 ms 6092 KB Output is correct
124 Correct 3296 ms 4388 KB Output is correct
125 Correct 709 ms 5420 KB Output is correct
126 Correct 730 ms 5672 KB Output is correct
127 Correct 822 ms 5476 KB Output is correct
128 Correct 730 ms 5380 KB Output is correct
129 Correct 674 ms 5432 KB Output is correct
130 Correct 776 ms 5392 KB Output is correct
131 Correct 3315 ms 5044 KB Output is correct
132 Correct 3111 ms 10772 KB Output is correct
133 Correct 2245 ms 15120 KB Output is correct
134 Correct 3310 ms 7724 KB Output is correct
135 Correct 1999 ms 16432 KB Output is correct
136 Correct 2815 ms 4924 KB Output is correct
137 Runtime error 172 ms 34944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
138 Halted 0 ms 0 KB -