oj.uz

Submission #161335

# Submission time Handle Problem Language Result Execution time Memory
161335 2019-11-01T21:07:33 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 13052 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 = 130;
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;
};
 
seg S[maxn];

ll ssz = 0;

vector <ll> 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> segsl;
vector <ll> segsr;
 
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 mrgl() {
	ll i, j;
	vector <ll> ANS;
	while (i != segsl.size() && j != lasts.size()) {
		if (cmpl(segsl[i], lasts[j])) {
			ANS.pb(segsl[i]);
			i++;
		}
		else {
			ANS.pb(lasts[j]);
			j++;
		}
	}
	for (; i < segsl.size(); i++) {
		ANS.pb(segsl[i]);
	}
	for (; j < lasts.size(); j++) {
		ANS.pb(lasts[j]);
	}
	segsl = ANS;
}

inline void mrgr() {
	ll i, j;
	vector <ll> ANS;
	while (i != segsr.size() && j != lasts.size()) {
		if (cmpr(segsr[i], lasts[j])) {
			ANS.pb(segsr[i]);
			i++;
		}
		else {
			ANS.pb(lasts[j]);
			j++;
		}
	}
	for (; i < segsr.size(); i++) {
		ANS.pb(segsr[i]);
	}
	for (; j < lasts.size(); j++) {
		ANS.pb(lasts[j]);
	}
	segsr = ANS;
}
 
inline void rebuild() { 
	ll q, w;
	ll blocki = 0;
	for (q = 0; q < block; q++) {
		R[q].clear();
		L[q].clear();
	}
	sort(lasts.begin(), lasts.end(), cmpl);
	mrgl();
	// sort(segs.begin(), segs.end(), cmpl);
	for (auto p : segsl) {
		IL[p] = -1;
		if (used[p]) {
			continue;
		}
		if (L[blocki].size() > block_sz) {
			blocki++;
		}
		IL[p] = blocki;
		L[blocki].pb(p);
	}
	sort(lasts.begin(), lasts.end(), cmpr);
	mrgr();
	lasts.clear();
	blocki = 0;
	// sort(segs.begin(), segs.end(), cmpr);
	for (auto p: segsr) {
		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.i);
	// S.pb(a);
	S[ssz] = a;
	ssz++;
	// 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 bpl(ll i, ll x) {
	ll l = -1, r = L[i].size(), M;
	while (r - l > 1) {
		M = (l + r) / 2;
		if (S[L[i][M]].sz() >= x) {
			r = M;
		}
		else {
			l = M;
		}
	}
	return r;
}

inline ll bpr(ll i, ll x) {
	ll l = -1, r = R[i].size(), M;
	while (r - l > 1) {
		M = (l + r) / 2;
		if (S[R[i][M]].sz() >= x) {
			r = M;
		}
		else {
			l = M;
		}
	}
	return r;
}
 
inline ll fastL(ll i, ll x) {
	if (L[i].empty()) {
		return 0;
	}
	seg good;
	good.l = 0; good.r = x - 1; 
	S[ssz] = good;
	ll j = (lower_bound(L[i].begin(), L[i].end(), ssz, cmpsz) - L[i].begin());
	// S.pop_back();
	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;
	S[ssz] = good;
	ll j = (lower_bound(R[i].begin(), R[i].end(), ssz, cmpsz) - R[i].begin());
	// S.pop_back();
	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;
		}
		ans += slowL(q, x, l);
	}
 
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q]]) {
			continue;
		}
		if (S[lasts[q]].l >= l && S[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]]) {
			continue;
		}
		if (S[lasts[q]].r <= r && S[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;
	// segsl.reserve(n);
	// segsr.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 = ssz;
			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:74: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:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < R[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void mrgl()':
segments.cpp:94:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (i != segsl.size() && j != lasts.size()) {
         ~~^~~~~~~~~~~~~~~
segments.cpp:94:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (i != segsl.size() && j != lasts.size()) {
                              ~~^~~~~~~~~~~~~~~
segments.cpp:104:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; i < segsl.size(); i++) {
         ~~^~~~~~~~~~~~~~
segments.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; j < lasts.size(); j++) {
         ~~^~~~~~~~~~~~~~
segments.cpp: In function 'void mrgr()':
segments.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (i != segsr.size() && j != lasts.size()) {
         ~~^~~~~~~~~~~~~~~
segments.cpp:116:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (i != segsr.size() && j != lasts.size()) {
                              ~~^~~~~~~~~~~~~~~
segments.cpp:126:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; i < segsr.size(); i++) {
         ~~^~~~~~~~~~~~~~
segments.cpp:129:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; j < lasts.size(); j++) {
         ~~^~~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:136:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:204: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:215: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:292: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:332: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:347:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:347:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:358:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:358:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:358:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
segments.cpp:362:5: warning: unused variable 'nxt' [-Wunused-variable]
  ll nxt = 0;
     ^~~
segments.cpp: In function 'void rebuild()':
segments.cpp:129:11: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for (; j < lasts.size(); j++) {
         ~~^~~~~~~~~~~~~~
segments.cpp:114:8: note: 'j' was declared here
  ll i, j;
        ^
segments.cpp:116:11: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while (i != segsr.size() && j != lasts.size()) {
         ~~^~~~~~~~~~~~~~~
segments.cpp:114:5: note: 'i' was declared here
  ll i, j;
     ^
segments.cpp:107:11: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for (; j < lasts.size(); j++) {
         ~~^~~~~~~~~~~~~~
segments.cpp:92:8: note: 'j' was declared here
  ll i, j;
        ^
segments.cpp:94:11: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while (i != segsl.size() && j != lasts.size()) {
         ~~^~~~~~~~~~~~~~~
segments.cpp:92:5: note: 'i' was declared here
  ll i, j;
     ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 1756 KB Output is correct
6 Correct 25 ms 1784 KB Output is correct
7 Correct 78 ms 1528 KB Output is correct
8 Correct 81 ms 1716 KB Output is correct
9 Correct 80 ms 1656 KB Output is correct
10 Correct 35 ms 1784 KB Output is correct
11 Correct 39 ms 1732 KB Output is correct
12 Correct 38 ms 1776 KB Output is correct
13 Correct 36 ms 1756 KB Output is correct
14 Correct 96 ms 1656 KB Output is correct
15 Correct 10 ms 1656 KB Output is correct
16 Correct 12 ms 1660 KB Output is correct
17 Correct 69 ms 1656 KB Output is correct
18 Correct 53 ms 1784 KB Output is correct
19 Correct 78 ms 1656 KB Output is correct
20 Correct 95 ms 1656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 4656 KB Output is correct
2 Correct 1945 ms 4848 KB Output is correct
3 Correct 1659 ms 4696 KB Output is correct
4 Correct 1591 ms 4764 KB Output is correct
5 Correct 359 ms 6420 KB Output is correct
6 Correct 220 ms 6260 KB Output is correct
7 Correct 1682 ms 4524 KB Output is correct
8 Correct 1679 ms 4548 KB Output is correct
9 Correct 1640 ms 4616 KB Output is correct
10 Correct 1870 ms 3304 KB Output is correct
11 Correct 1896 ms 3572 KB Output is correct
12 Correct 1155 ms 5472 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 3132 KB Output is correct
2 Correct 298 ms 3252 KB Output is correct
3 Correct 315 ms 3384 KB Output is correct
4 Correct 200 ms 3240 KB Output is correct
5 Correct 812 ms 5596 KB Output is correct
6 Correct 1058 ms 5020 KB Output is correct
7 Correct 944 ms 5488 KB Output is correct
8 Correct 252 ms 6376 KB Output is correct
9 Correct 753 ms 7464 KB Output is correct
10 Correct 2260 ms 6508 KB Output is correct
11 Correct 1723 ms 3900 KB Output is correct
12 Correct 2220 ms 6736 KB Output is correct
13 Correct 2593 ms 6164 KB Output is correct
14 Correct 3406 ms 5104 KB Output is correct
15 Correct 3488 ms 4640 KB Output is correct
16 Correct 3157 ms 4084 KB Output is correct
17 Correct 1321 ms 4556 KB Output is correct
18 Correct 1270 ms 4544 KB Output is correct
19 Correct 1272 ms 4520 KB Output is correct
20 Correct 1249 ms 4572 KB Output is correct
21 Correct 2105 ms 3960 KB Output is correct
22 Correct 3375 ms 5132 KB Output is correct
23 Correct 3099 ms 5472 KB Output is correct
24 Correct 3463 ms 5172 KB Output is correct
25 Correct 234 ms 3516 KB Output is correct
26 Correct 204 ms 3396 KB Output is correct
27 Correct 232 ms 3352 KB Output is correct
28 Correct 209 ms 3264 KB Output is correct
29 Correct 2793 ms 6220 KB Output is correct
30 Correct 2790 ms 6256 KB Output is correct
31 Correct 710 ms 6832 KB Output is correct
32 Correct 2309 ms 6480 KB Output is correct
33 Correct 2611 ms 6304 KB Output is correct
34 Correct 3463 ms 4800 KB Output is correct
35 Correct 3061 ms 5792 KB Output is correct
36 Correct 2329 ms 6344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3124 KB Output is correct
2 Correct 188 ms 3092 KB Output is correct
3 Correct 195 ms 3232 KB Output is correct
4 Correct 209 ms 3252 KB Output is correct
5 Correct 954 ms 5672 KB Output is correct
6 Correct 1783 ms 3192 KB Output is correct
7 Correct 765 ms 6060 KB Output is correct
8 Correct 1849 ms 3408 KB Output is correct
9 Correct 3546 ms 5204 KB Output is correct
10 Correct 2035 ms 7072 KB Output is correct
11 Correct 3297 ms 3916 KB Output is correct
12 Correct 485 ms 6504 KB Output is correct
13 Correct 2708 ms 6116 KB Output is correct
14 Correct 3503 ms 4648 KB Output is correct
15 Correct 849 ms 7112 KB Output is correct
16 Correct 2498 ms 6364 KB Output is correct
17 Correct 1691 ms 4572 KB Output is correct
18 Correct 1672 ms 4468 KB Output is correct
19 Correct 1849 ms 4412 KB Output is correct
20 Correct 1661 ms 4528 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 1756 KB Output is correct
6 Correct 25 ms 1784 KB Output is correct
7 Correct 78 ms 1528 KB Output is correct
8 Correct 81 ms 1716 KB Output is correct
9 Correct 80 ms 1656 KB Output is correct
10 Correct 35 ms 1784 KB Output is correct
11 Correct 39 ms 1732 KB Output is correct
12 Correct 38 ms 1776 KB Output is correct
13 Correct 36 ms 1756 KB Output is correct
14 Correct 96 ms 1656 KB Output is correct
15 Correct 10 ms 1656 KB Output is correct
16 Correct 12 ms 1660 KB Output is correct
17 Correct 69 ms 1656 KB Output is correct
18 Correct 53 ms 1784 KB Output is correct
19 Correct 78 ms 1656 KB Output is correct
20 Correct 95 ms 1656 KB Output is correct
21 Correct 1690 ms 4656 KB Output is correct
22 Correct 1945 ms 4848 KB Output is correct
23 Correct 1659 ms 4696 KB Output is correct
24 Correct 1591 ms 4764 KB Output is correct
25 Correct 359 ms 6420 KB Output is correct
26 Correct 220 ms 6260 KB Output is correct
27 Correct 1682 ms 4524 KB Output is correct
28 Correct 1679 ms 4548 KB Output is correct
29 Correct 1640 ms 4616 KB Output is correct
30 Correct 1870 ms 3304 KB Output is correct
31 Correct 1896 ms 3572 KB Output is correct
32 Correct 1155 ms 5472 KB Output is correct
33 Correct 185 ms 3124 KB Output is correct
34 Correct 188 ms 3092 KB Output is correct
35 Correct 195 ms 3232 KB Output is correct
36 Correct 209 ms 3252 KB Output is correct
37 Correct 954 ms 5672 KB Output is correct
38 Correct 1783 ms 3192 KB Output is correct
39 Correct 765 ms 6060 KB Output is correct
40 Correct 1849 ms 3408 KB Output is correct
41 Correct 3546 ms 5204 KB Output is correct
42 Correct 2035 ms 7072 KB Output is correct
43 Correct 3297 ms 3916 KB Output is correct
44 Correct 485 ms 6504 KB Output is correct
45 Correct 2708 ms 6116 KB Output is correct
46 Correct 3503 ms 4648 KB Output is correct
47 Correct 849 ms 7112 KB Output is correct
48 Correct 2498 ms 6364 KB Output is correct
49 Correct 1691 ms 4572 KB Output is correct
50 Correct 1672 ms 4468 KB Output is correct
51 Correct 1849 ms 4412 KB Output is correct
52 Correct 1661 ms 4528 KB Output is correct
53 Correct 221 ms 3068 KB Output is correct
54 Correct 222 ms 3028 KB Output is correct
55 Correct 189 ms 3124 KB Output is correct
56 Correct 198 ms 3084 KB Output is correct
57 Correct 1916 ms 3640 KB Output is correct
58 Correct 1733 ms 2704 KB Output is correct
59 Correct 1677 ms 4892 KB Output is correct
60 Correct 1622 ms 2680 KB Output is correct
61 Correct 2761 ms 6148 KB Output is correct
62 Correct 1116 ms 7504 KB Output is correct
63 Correct 617 ms 6680 KB Output is correct
64 Correct 1194 ms 7436 KB Output is correct
65 Correct 3484 ms 4484 KB Output is correct
66 Correct 3349 ms 4336 KB Output is correct
67 Correct 2438 ms 6436 KB Output is correct
68 Correct 3150 ms 5564 KB Output is correct
69 Correct 1660 ms 4660 KB Output is correct
70 Correct 1664 ms 4576 KB Output is correct
71 Correct 1716 ms 4660 KB Output is correct
72 Correct 1646 ms 4732 KB Output is correct
73 Correct 3624 ms 4644 KB Output is correct
74 Correct 3243 ms 5600 KB Output is correct
75 Correct 247 ms 6308 KB Output is correct
76 Correct 568 ms 6672 KB Output is correct
77 Correct 207 ms 3288 KB Output is correct
78 Correct 233 ms 3120 KB Output is correct
79 Correct 215 ms 3148 KB Output is correct
80 Correct 242 ms 3364 KB Output is correct
81 Correct 3313 ms 5448 KB Output is correct
82 Correct 3680 ms 4608 KB Output is correct
83 Correct 3102 ms 4124 KB Output is correct
84 Correct 3251 ms 5476 KB Output is correct
85 Correct 2367 ms 6360 KB Output is correct
86 Correct 2278 ms 6640 KB Output is correct
87 Correct 3976 ms 5032 KB Output is correct
88 Correct 3127 ms 4108 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 1756 KB Output is correct
6 Correct 25 ms 1784 KB Output is correct
7 Correct 78 ms 1528 KB Output is correct
8 Correct 81 ms 1716 KB Output is correct
9 Correct 80 ms 1656 KB Output is correct
10 Correct 35 ms 1784 KB Output is correct
11 Correct 39 ms 1732 KB Output is correct
12 Correct 38 ms 1776 KB Output is correct
13 Correct 36 ms 1756 KB Output is correct
14 Correct 96 ms 1656 KB Output is correct
15 Correct 10 ms 1656 KB Output is correct
16 Correct 12 ms 1660 KB Output is correct
17 Correct 69 ms 1656 KB Output is correct
18 Correct 53 ms 1784 KB Output is correct
19 Correct 78 ms 1656 KB Output is correct
20 Correct 95 ms 1656 KB Output is correct
21 Correct 1690 ms 4656 KB Output is correct
22 Correct 1945 ms 4848 KB Output is correct
23 Correct 1659 ms 4696 KB Output is correct
24 Correct 1591 ms 4764 KB Output is correct
25 Correct 359 ms 6420 KB Output is correct
26 Correct 220 ms 6260 KB Output is correct
27 Correct 1682 ms 4524 KB Output is correct
28 Correct 1679 ms 4548 KB Output is correct
29 Correct 1640 ms 4616 KB Output is correct
30 Correct 1870 ms 3304 KB Output is correct
31 Correct 1896 ms 3572 KB Output is correct
32 Correct 1155 ms 5472 KB Output is correct
33 Correct 225 ms 3132 KB Output is correct
34 Correct 298 ms 3252 KB Output is correct
35 Correct 315 ms 3384 KB Output is correct
36 Correct 200 ms 3240 KB Output is correct
37 Correct 812 ms 5596 KB Output is correct
38 Correct 1058 ms 5020 KB Output is correct
39 Correct 944 ms 5488 KB Output is correct
40 Correct 252 ms 6376 KB Output is correct
41 Correct 753 ms 7464 KB Output is correct
42 Correct 2260 ms 6508 KB Output is correct
43 Correct 1723 ms 3900 KB Output is correct
44 Correct 2220 ms 6736 KB Output is correct
45 Correct 2593 ms 6164 KB Output is correct
46 Correct 3406 ms 5104 KB Output is correct
47 Correct 3488 ms 4640 KB Output is correct
48 Correct 3157 ms 4084 KB Output is correct
49 Correct 1321 ms 4556 KB Output is correct
50 Correct 1270 ms 4544 KB Output is correct
51 Correct 1272 ms 4520 KB Output is correct
52 Correct 1249 ms 4572 KB Output is correct
53 Correct 2105 ms 3960 KB Output is correct
54 Correct 3375 ms 5132 KB Output is correct
55 Correct 3099 ms 5472 KB Output is correct
56 Correct 3463 ms 5172 KB Output is correct
57 Correct 234 ms 3516 KB Output is correct
58 Correct 204 ms 3396 KB Output is correct
59 Correct 232 ms 3352 KB Output is correct
60 Correct 209 ms 3264 KB Output is correct
61 Correct 2793 ms 6220 KB Output is correct
62 Correct 2790 ms 6256 KB Output is correct
63 Correct 710 ms 6832 KB Output is correct
64 Correct 2309 ms 6480 KB Output is correct
65 Correct 2611 ms 6304 KB Output is correct
66 Correct 3463 ms 4800 KB Output is correct
67 Correct 3061 ms 5792 KB Output is correct
68 Correct 2329 ms 6344 KB Output is correct
69 Correct 185 ms 3124 KB Output is correct
70 Correct 188 ms 3092 KB Output is correct
71 Correct 195 ms 3232 KB Output is correct
72 Correct 209 ms 3252 KB Output is correct
73 Correct 954 ms 5672 KB Output is correct
74 Correct 1783 ms 3192 KB Output is correct
75 Correct 765 ms 6060 KB Output is correct
76 Correct 1849 ms 3408 KB Output is correct
77 Correct 3546 ms 5204 KB Output is correct
78 Correct 2035 ms 7072 KB Output is correct
79 Correct 3297 ms 3916 KB Output is correct
80 Correct 485 ms 6504 KB Output is correct
81 Correct 2708 ms 6116 KB Output is correct
82 Correct 3503 ms 4648 KB Output is correct
83 Correct 849 ms 7112 KB Output is correct
84 Correct 2498 ms 6364 KB Output is correct
85 Correct 1691 ms 4572 KB Output is correct
86 Correct 1672 ms 4468 KB Output is correct
87 Correct 1849 ms 4412 KB Output is correct
88 Correct 1661 ms 4528 KB Output is correct
89 Correct 221 ms 3068 KB Output is correct
90 Correct 222 ms 3028 KB Output is correct
91 Correct 189 ms 3124 KB Output is correct
92 Correct 198 ms 3084 KB Output is correct
93 Correct 1916 ms 3640 KB Output is correct
94 Correct 1733 ms 2704 KB Output is correct
95 Correct 1677 ms 4892 KB Output is correct
96 Correct 1622 ms 2680 KB Output is correct
97 Correct 2761 ms 6148 KB Output is correct
98 Correct 1116 ms 7504 KB Output is correct
99 Correct 617 ms 6680 KB Output is correct
100 Correct 1194 ms 7436 KB Output is correct
101 Correct 3484 ms 4484 KB Output is correct
102 Correct 3349 ms 4336 KB Output is correct
103 Correct 2438 ms 6436 KB Output is correct
104 Correct 3150 ms 5564 KB Output is correct
105 Correct 1660 ms 4660 KB Output is correct
106 Correct 1664 ms 4576 KB Output is correct
107 Correct 1716 ms 4660 KB Output is correct
108 Correct 1646 ms 4732 KB Output is correct
109 Correct 3624 ms 4644 KB Output is correct
110 Correct 3243 ms 5600 KB Output is correct
111 Correct 247 ms 6308 KB Output is correct
112 Correct 568 ms 6672 KB Output is correct
113 Correct 207 ms 3288 KB Output is correct
114 Correct 233 ms 3120 KB Output is correct
115 Correct 215 ms 3148 KB Output is correct
116 Correct 242 ms 3364 KB Output is correct
117 Correct 3313 ms 5448 KB Output is correct
118 Correct 3680 ms 4608 KB Output is correct
119 Correct 3102 ms 4124 KB Output is correct
120 Correct 3251 ms 5476 KB Output is correct
121 Correct 2367 ms 6360 KB Output is correct
122 Correct 2278 ms 6640 KB Output is correct
123 Correct 3976 ms 5032 KB Output is correct
124 Correct 3127 ms 4108 KB Output is correct
125 Correct 474 ms 5176 KB Output is correct
126 Correct 519 ms 5108 KB Output is correct
127 Correct 702 ms 5204 KB Output is correct
128 Correct 515 ms 5124 KB Output is correct
129 Correct 443 ms 5080 KB Output is correct
130 Correct 553 ms 5220 KB Output is correct
131 Correct 4195 ms 3960 KB Output is correct
132 Correct 4569 ms 6800 KB Output is correct
133 Correct 3475 ms 8692 KB Output is correct
134 Correct 4683 ms 4424 KB Output is correct
135 Correct 3321 ms 8844 KB Output is correct
136 Correct 2890 ms 2936 KB Output is correct
137 Correct 2183 ms 13052 KB Output is correct
138 Execution timed out 5103 ms 9084 KB Time limit exceeded
139 Halted 0 ms 0 KB -