oj.uz

Submission #161311

# Submission time Handle Problem Language Result Execution time Memory
161311 2019-11-01T19:22:55 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 11748 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 = 120;
const ll block_sz = (maxn + block - 1) / block;
 
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;

vector <seg> lasts;
 
inline bool cmpl(const ll& a, const ll& b) {
	return S[a].l < S[b].l;
}
 
inline bool cmpr(const ll& a, const ll& b) {
	return S[a].r < S[b].r;
}
 
inline bool cmpsz(const ll& a, const ll& b) {
	return S[a].sz() < S[b].sz();
}
 
vector <ll> segs;
 
vector <ll> R[block];
 
vector <ll> 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], S[L[q][w]].l);
		MXL[q] = max(MXL[q], S[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], S[R[q][w]].r);
		MXR[q] = max(MXR[q], S[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) {
		IL[p] = -1;
		if (used[p]) {
			continue;
		}
		if (L[blocki].size() > block_sz) {
			blocki++;
		}
		IL[p] = blocki;
		L[blocki].pb(p);
	}
	blocki = 0;
	sort(segs.begin(), segs.end(), cmpr);
	for (auto p: segs) {
		IR[p] = -1;
		if (used[p]) {
			continue;
		}
		if (R[blocki].size() > block_sz) {
			blocki++;
		}
		IR[p] = 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.i);
	IL[a.i] = IR[a.i] = -1;
}
 
inline void del(seg b) { 
	ll il = IL[b.i], ir = IR[b.i];
	used[b.i] = 1;
	if (il == -1) {
		return;
	}
	L[il].erase(find(L[il].begin(), L[il].end(), b.i));
	R[ir].erase(find(R[ir].begin(), R[ir].end(), b.i));
	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 (S[L[i][q]].l >= l && S[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 (S[R[i][q]].r <= r && S[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; 
	S.pb(good);
	ll j = (lower_bound(L[i].begin(), L[i].end(), S.size() - 1, cmpsz) - L[i].begin());
	S.pop_back();
	return (ll)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;
	S.pb(good);
	ll j = (lower_bound(R[i].begin(), R[i].end(), S.size() - 1, cmpsz) - R[i].begin());
	S.pop_back();
	return (ll)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;
	segs.reserve(n);
	S.reserve(n);
	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:75: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:86: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:93:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:155: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:166: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:217: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:257: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:272:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:272:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:283:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:283:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:283:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
segments.cpp:287:5: warning: unused variable 'nxt' [-Wunused-variable]
  ll nxt = 0;
     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1400 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 19 ms 1656 KB Output is correct
6 Correct 24 ms 1656 KB Output is correct
7 Correct 38 ms 1528 KB Output is correct
8 Correct 77 ms 1656 KB Output is correct
9 Correct 83 ms 1676 KB Output is correct
10 Correct 37 ms 1784 KB Output is correct
11 Correct 34 ms 1656 KB Output is correct
12 Correct 35 ms 1656 KB Output is correct
13 Correct 35 ms 1784 KB Output is correct
14 Correct 87 ms 1656 KB Output is correct
15 Correct 10 ms 1528 KB Output is correct
16 Correct 13 ms 1528 KB Output is correct
17 Correct 64 ms 1528 KB Output is correct
18 Correct 55 ms 1784 KB Output is correct
19 Correct 74 ms 1528 KB Output is correct
20 Correct 90 ms 1656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 4864 KB Output is correct
2 Correct 1672 ms 4896 KB Output is correct
3 Correct 1672 ms 5028 KB Output is correct
4 Correct 1605 ms 5076 KB Output is correct
5 Correct 338 ms 6380 KB Output is correct
6 Correct 226 ms 6548 KB Output is correct
7 Correct 1664 ms 4724 KB Output is correct
8 Correct 1677 ms 4896 KB Output is correct
9 Correct 1722 ms 4976 KB Output is correct
10 Correct 1793 ms 3712 KB Output is correct
11 Correct 1918 ms 3960 KB Output is correct
12 Correct 1202 ms 5760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 3248 KB Output is correct
2 Correct 244 ms 3064 KB Output is correct
3 Correct 375 ms 3064 KB Output is correct
4 Correct 264 ms 3064 KB Output is correct
5 Correct 834 ms 5676 KB Output is correct
6 Correct 1112 ms 5420 KB Output is correct
7 Correct 963 ms 5520 KB Output is correct
8 Correct 254 ms 6644 KB Output is correct
9 Correct 791 ms 6636 KB Output is correct
10 Correct 2444 ms 5836 KB Output is correct
11 Correct 1985 ms 3200 KB Output is correct
12 Correct 2358 ms 5748 KB Output is correct
13 Correct 2854 ms 5584 KB Output is correct
14 Correct 3704 ms 4392 KB Output is correct
15 Correct 3685 ms 4388 KB Output is correct
16 Correct 3350 ms 3884 KB Output is correct
17 Correct 1281 ms 4976 KB Output is correct
18 Correct 1534 ms 5204 KB Output is correct
19 Correct 1274 ms 4976 KB Output is correct
20 Correct 1268 ms 5104 KB Output is correct
21 Correct 2338 ms 3516 KB Output is correct
22 Correct 3717 ms 4640 KB Output is correct
23 Correct 3383 ms 5140 KB Output is correct
24 Correct 3721 ms 4824 KB Output is correct
25 Correct 308 ms 3096 KB Output is correct
26 Correct 272 ms 3196 KB Output is correct
27 Correct 363 ms 3124 KB Output is correct
28 Correct 284 ms 3112 KB Output is correct
29 Correct 3043 ms 5208 KB Output is correct
30 Correct 3072 ms 5360 KB Output is correct
31 Correct 745 ms 6644 KB Output is correct
32 Correct 2525 ms 5620 KB Output is correct
33 Correct 2913 ms 5420 KB Output is correct
34 Correct 3778 ms 4212 KB Output is correct
35 Correct 3232 ms 4948 KB Output is correct
36 Correct 2489 ms 5616 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 3192 KB Output is correct
2 Correct 266 ms 3192 KB Output is correct
3 Correct 262 ms 3088 KB Output is correct
4 Correct 269 ms 3240 KB Output is correct
5 Correct 974 ms 6124 KB Output is correct
6 Correct 1770 ms 3640 KB Output is correct
7 Correct 756 ms 6124 KB Output is correct
8 Correct 1814 ms 3764 KB Output is correct
9 Correct 3840 ms 4592 KB Output is correct
10 Correct 2251 ms 5996 KB Output is correct
11 Correct 3382 ms 3896 KB Output is correct
12 Correct 441 ms 6892 KB Output is correct
13 Correct 3006 ms 5452 KB Output is correct
14 Correct 3765 ms 4496 KB Output is correct
15 Correct 926 ms 6508 KB Output is correct
16 Correct 2744 ms 5488 KB Output is correct
17 Correct 1944 ms 5108 KB Output is correct
18 Correct 1652 ms 4996 KB Output is correct
19 Correct 1681 ms 4848 KB Output is correct
20 Correct 1680 ms 5004 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1400 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 19 ms 1656 KB Output is correct
6 Correct 24 ms 1656 KB Output is correct
7 Correct 38 ms 1528 KB Output is correct
8 Correct 77 ms 1656 KB Output is correct
9 Correct 83 ms 1676 KB Output is correct
10 Correct 37 ms 1784 KB Output is correct
11 Correct 34 ms 1656 KB Output is correct
12 Correct 35 ms 1656 KB Output is correct
13 Correct 35 ms 1784 KB Output is correct
14 Correct 87 ms 1656 KB Output is correct
15 Correct 10 ms 1528 KB Output is correct
16 Correct 13 ms 1528 KB Output is correct
17 Correct 64 ms 1528 KB Output is correct
18 Correct 55 ms 1784 KB Output is correct
19 Correct 74 ms 1528 KB Output is correct
20 Correct 90 ms 1656 KB Output is correct
21 Correct 1664 ms 4864 KB Output is correct
22 Correct 1672 ms 4896 KB Output is correct
23 Correct 1672 ms 5028 KB Output is correct
24 Correct 1605 ms 5076 KB Output is correct
25 Correct 338 ms 6380 KB Output is correct
26 Correct 226 ms 6548 KB Output is correct
27 Correct 1664 ms 4724 KB Output is correct
28 Correct 1677 ms 4896 KB Output is correct
29 Correct 1722 ms 4976 KB Output is correct
30 Correct 1793 ms 3712 KB Output is correct
31 Correct 1918 ms 3960 KB Output is correct
32 Correct 1202 ms 5760 KB Output is correct
33 Correct 261 ms 3192 KB Output is correct
34 Correct 266 ms 3192 KB Output is correct
35 Correct 262 ms 3088 KB Output is correct
36 Correct 269 ms 3240 KB Output is correct
37 Correct 974 ms 6124 KB Output is correct
38 Correct 1770 ms 3640 KB Output is correct
39 Correct 756 ms 6124 KB Output is correct
40 Correct 1814 ms 3764 KB Output is correct
41 Correct 3840 ms 4592 KB Output is correct
42 Correct 2251 ms 5996 KB Output is correct
43 Correct 3382 ms 3896 KB Output is correct
44 Correct 441 ms 6892 KB Output is correct
45 Correct 3006 ms 5452 KB Output is correct
46 Correct 3765 ms 4496 KB Output is correct
47 Correct 926 ms 6508 KB Output is correct
48 Correct 2744 ms 5488 KB Output is correct
49 Correct 1944 ms 5108 KB Output is correct
50 Correct 1652 ms 4996 KB Output is correct
51 Correct 1681 ms 4848 KB Output is correct
52 Correct 1680 ms 5004 KB Output is correct
53 Correct 293 ms 3172 KB Output is correct
54 Correct 293 ms 3164 KB Output is correct
55 Correct 254 ms 3196 KB Output is correct
56 Correct 272 ms 3104 KB Output is correct
57 Correct 1928 ms 4340 KB Output is correct
58 Correct 1619 ms 3512 KB Output is correct
59 Correct 1431 ms 5404 KB Output is correct
60 Correct 1556 ms 3336 KB Output is correct
61 Correct 2985 ms 5116 KB Output is correct
62 Correct 1160 ms 6616 KB Output is correct
63 Correct 677 ms 6636 KB Output is correct
64 Correct 1101 ms 6504 KB Output is correct
65 Correct 3742 ms 4008 KB Output is correct
66 Correct 3489 ms 3792 KB Output is correct
67 Correct 2687 ms 5488 KB Output is correct
68 Correct 3401 ms 4632 KB Output is correct
69 Correct 1661 ms 4868 KB Output is correct
70 Correct 1707 ms 4860 KB Output is correct
71 Correct 1687 ms 4964 KB Output is correct
72 Correct 1649 ms 4872 KB Output is correct
73 Correct 3843 ms 3828 KB Output is correct
74 Correct 3586 ms 4716 KB Output is correct
75 Correct 250 ms 6380 KB Output is correct
76 Correct 634 ms 6384 KB Output is correct
77 Correct 275 ms 3076 KB Output is correct
78 Correct 266 ms 2808 KB Output is correct
79 Correct 304 ms 2908 KB Output is correct
80 Correct 282 ms 2852 KB Output is correct
81 Correct 3758 ms 4696 KB Output is correct
82 Correct 3989 ms 3960 KB Output is correct
83 Correct 3447 ms 3540 KB Output is correct
84 Correct 3660 ms 4592 KB Output is correct
85 Correct 2655 ms 5248 KB Output is correct
86 Correct 2497 ms 5476 KB Output is correct
87 Correct 3837 ms 4208 KB Output is correct
88 Correct 3343 ms 3472 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1400 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 19 ms 1656 KB Output is correct
6 Correct 24 ms 1656 KB Output is correct
7 Correct 38 ms 1528 KB Output is correct
8 Correct 77 ms 1656 KB Output is correct
9 Correct 83 ms 1676 KB Output is correct
10 Correct 37 ms 1784 KB Output is correct
11 Correct 34 ms 1656 KB Output is correct
12 Correct 35 ms 1656 KB Output is correct
13 Correct 35 ms 1784 KB Output is correct
14 Correct 87 ms 1656 KB Output is correct
15 Correct 10 ms 1528 KB Output is correct
16 Correct 13 ms 1528 KB Output is correct
17 Correct 64 ms 1528 KB Output is correct
18 Correct 55 ms 1784 KB Output is correct
19 Correct 74 ms 1528 KB Output is correct
20 Correct 90 ms 1656 KB Output is correct
21 Correct 1664 ms 4864 KB Output is correct
22 Correct 1672 ms 4896 KB Output is correct
23 Correct 1672 ms 5028 KB Output is correct
24 Correct 1605 ms 5076 KB Output is correct
25 Correct 338 ms 6380 KB Output is correct
26 Correct 226 ms 6548 KB Output is correct
27 Correct 1664 ms 4724 KB Output is correct
28 Correct 1677 ms 4896 KB Output is correct
29 Correct 1722 ms 4976 KB Output is correct
30 Correct 1793 ms 3712 KB Output is correct
31 Correct 1918 ms 3960 KB Output is correct
32 Correct 1202 ms 5760 KB Output is correct
33 Correct 298 ms 3248 KB Output is correct
34 Correct 244 ms 3064 KB Output is correct
35 Correct 375 ms 3064 KB Output is correct
36 Correct 264 ms 3064 KB Output is correct
37 Correct 834 ms 5676 KB Output is correct
38 Correct 1112 ms 5420 KB Output is correct
39 Correct 963 ms 5520 KB Output is correct
40 Correct 254 ms 6644 KB Output is correct
41 Correct 791 ms 6636 KB Output is correct
42 Correct 2444 ms 5836 KB Output is correct
43 Correct 1985 ms 3200 KB Output is correct
44 Correct 2358 ms 5748 KB Output is correct
45 Correct 2854 ms 5584 KB Output is correct
46 Correct 3704 ms 4392 KB Output is correct
47 Correct 3685 ms 4388 KB Output is correct
48 Correct 3350 ms 3884 KB Output is correct
49 Correct 1281 ms 4976 KB Output is correct
50 Correct 1534 ms 5204 KB Output is correct
51 Correct 1274 ms 4976 KB Output is correct
52 Correct 1268 ms 5104 KB Output is correct
53 Correct 2338 ms 3516 KB Output is correct
54 Correct 3717 ms 4640 KB Output is correct
55 Correct 3383 ms 5140 KB Output is correct
56 Correct 3721 ms 4824 KB Output is correct
57 Correct 308 ms 3096 KB Output is correct
58 Correct 272 ms 3196 KB Output is correct
59 Correct 363 ms 3124 KB Output is correct
60 Correct 284 ms 3112 KB Output is correct
61 Correct 3043 ms 5208 KB Output is correct
62 Correct 3072 ms 5360 KB Output is correct
63 Correct 745 ms 6644 KB Output is correct
64 Correct 2525 ms 5620 KB Output is correct
65 Correct 2913 ms 5420 KB Output is correct
66 Correct 3778 ms 4212 KB Output is correct
67 Correct 3232 ms 4948 KB Output is correct
68 Correct 2489 ms 5616 KB Output is correct
69 Correct 261 ms 3192 KB Output is correct
70 Correct 266 ms 3192 KB Output is correct
71 Correct 262 ms 3088 KB Output is correct
72 Correct 269 ms 3240 KB Output is correct
73 Correct 974 ms 6124 KB Output is correct
74 Correct 1770 ms 3640 KB Output is correct
75 Correct 756 ms 6124 KB Output is correct
76 Correct 1814 ms 3764 KB Output is correct
77 Correct 3840 ms 4592 KB Output is correct
78 Correct 2251 ms 5996 KB Output is correct
79 Correct 3382 ms 3896 KB Output is correct
80 Correct 441 ms 6892 KB Output is correct
81 Correct 3006 ms 5452 KB Output is correct
82 Correct 3765 ms 4496 KB Output is correct
83 Correct 926 ms 6508 KB Output is correct
84 Correct 2744 ms 5488 KB Output is correct
85 Correct 1944 ms 5108 KB Output is correct
86 Correct 1652 ms 4996 KB Output is correct
87 Correct 1681 ms 4848 KB Output is correct
88 Correct 1680 ms 5004 KB Output is correct
89 Correct 293 ms 3172 KB Output is correct
90 Correct 293 ms 3164 KB Output is correct
91 Correct 254 ms 3196 KB Output is correct
92 Correct 272 ms 3104 KB Output is correct
93 Correct 1928 ms 4340 KB Output is correct
94 Correct 1619 ms 3512 KB Output is correct
95 Correct 1431 ms 5404 KB Output is correct
96 Correct 1556 ms 3336 KB Output is correct
97 Correct 2985 ms 5116 KB Output is correct
98 Correct 1160 ms 6616 KB Output is correct
99 Correct 677 ms 6636 KB Output is correct
100 Correct 1101 ms 6504 KB Output is correct
101 Correct 3742 ms 4008 KB Output is correct
102 Correct 3489 ms 3792 KB Output is correct
103 Correct 2687 ms 5488 KB Output is correct
104 Correct 3401 ms 4632 KB Output is correct
105 Correct 1661 ms 4868 KB Output is correct
106 Correct 1707 ms 4860 KB Output is correct
107 Correct 1687 ms 4964 KB Output is correct
108 Correct 1649 ms 4872 KB Output is correct
109 Correct 3843 ms 3828 KB Output is correct
110 Correct 3586 ms 4716 KB Output is correct
111 Correct 250 ms 6380 KB Output is correct
112 Correct 634 ms 6384 KB Output is correct
113 Correct 275 ms 3076 KB Output is correct
114 Correct 266 ms 2808 KB Output is correct
115 Correct 304 ms 2908 KB Output is correct
116 Correct 282 ms 2852 KB Output is correct
117 Correct 3758 ms 4696 KB Output is correct
118 Correct 3989 ms 3960 KB Output is correct
119 Correct 3447 ms 3540 KB Output is correct
120 Correct 3660 ms 4592 KB Output is correct
121 Correct 2655 ms 5248 KB Output is correct
122 Correct 2497 ms 5476 KB Output is correct
123 Correct 3837 ms 4208 KB Output is correct
124 Correct 3343 ms 3472 KB Output is correct
125 Correct 842 ms 4068 KB Output is correct
126 Correct 972 ms 4020 KB Output is correct
127 Correct 993 ms 4176 KB Output is correct
128 Correct 912 ms 4216 KB Output is correct
129 Correct 834 ms 4088 KB Output is correct
130 Correct 897 ms 3992 KB Output is correct
131 Correct 4054 ms 4372 KB Output is correct
132 Correct 4593 ms 7020 KB Output is correct
133 Correct 4019 ms 8556 KB Output is correct
134 Correct 4718 ms 4968 KB Output is correct
135 Correct 3245 ms 10252 KB Output is correct
136 Correct 2814 ms 4992 KB Output is correct
137 Correct 2520 ms 11748 KB Output is correct
138 Execution timed out 5009 ms 7920 KB Time limit exceeded
139 Halted 0 ms 0 KB -