oj.uz

Submission #161330

# Submission time Handle Problem Language Result Execution time Memory
161330 2019-11-01T20:34:57 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 17364 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 = 180;
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 1784 KB Output is correct
2 Correct 3 ms 1840 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 9 ms 2040 KB Output is correct
5 Correct 17 ms 2128 KB Output is correct
6 Correct 21 ms 2044 KB Output is correct
7 Correct 38 ms 2036 KB Output is correct
8 Correct 57 ms 2148 KB Output is correct
9 Correct 60 ms 2140 KB Output is correct
10 Correct 26 ms 2168 KB Output is correct
11 Correct 32 ms 2040 KB Output is correct
12 Correct 33 ms 2040 KB Output is correct
13 Correct 26 ms 2168 KB Output is correct
14 Correct 67 ms 2040 KB Output is correct
15 Correct 9 ms 1912 KB Output is correct
16 Correct 12 ms 2040 KB Output is correct
17 Correct 70 ms 2076 KB Output is correct
18 Correct 41 ms 2040 KB Output is correct
19 Correct 66 ms 2088 KB Output is correct
20 Correct 63 ms 2168 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1532 ms 4748 KB Output is correct
2 Correct 1521 ms 5592 KB Output is correct
3 Correct 1504 ms 5808 KB Output is correct
4 Correct 1452 ms 5808 KB Output is correct
5 Correct 326 ms 7040 KB Output is correct
6 Correct 221 ms 7160 KB Output is correct
7 Correct 1609 ms 5288 KB Output is correct
8 Correct 1515 ms 5464 KB Output is correct
9 Correct 1555 ms 5316 KB Output is correct
10 Correct 1528 ms 4252 KB Output is correct
11 Correct 1652 ms 4372 KB Output is correct
12 Correct 1145 ms 6112 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 3792 KB Output is correct
2 Correct 176 ms 3676 KB Output is correct
3 Correct 318 ms 3700 KB Output is correct
4 Correct 181 ms 3712 KB Output is correct
5 Correct 685 ms 5620 KB Output is correct
6 Correct 887 ms 5124 KB Output is correct
7 Correct 888 ms 5632 KB Output is correct
8 Correct 228 ms 6400 KB Output is correct
9 Correct 560 ms 7512 KB Output is correct
10 Correct 1628 ms 6540 KB Output is correct
11 Correct 1475 ms 3920 KB Output is correct
12 Correct 1547 ms 6868 KB Output is correct
13 Correct 1870 ms 6728 KB Output is correct
14 Correct 2353 ms 5576 KB Output is correct
15 Correct 2334 ms 5332 KB Output is correct
16 Correct 2227 ms 4844 KB Output is correct
17 Correct 1056 ms 5084 KB Output is correct
18 Correct 1047 ms 5252 KB Output is correct
19 Correct 1053 ms 5156 KB Output is correct
20 Correct 1052 ms 5284 KB Output is correct
21 Correct 1560 ms 4488 KB Output is correct
22 Correct 2386 ms 5764 KB Output is correct
23 Correct 2146 ms 6160 KB Output is correct
24 Correct 2413 ms 5944 KB Output is correct
25 Correct 231 ms 4404 KB Output is correct
26 Correct 187 ms 4420 KB Output is correct
27 Correct 214 ms 4240 KB Output is correct
28 Correct 195 ms 4404 KB Output is correct
29 Correct 2053 ms 6752 KB Output is correct
30 Correct 2025 ms 6768 KB Output is correct
31 Correct 524 ms 8396 KB Output is correct
32 Correct 1637 ms 7404 KB Output is correct
33 Correct 1803 ms 7016 KB Output is correct
34 Correct 2388 ms 5676 KB Output is correct
35 Correct 2127 ms 6516 KB Output is correct
36 Correct 1627 ms 7472 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 4188 KB Output is correct
2 Correct 190 ms 4136 KB Output is correct
3 Correct 179 ms 4056 KB Output is correct
4 Correct 198 ms 4044 KB Output is correct
5 Correct 945 ms 6344 KB Output is correct
6 Correct 1433 ms 4724 KB Output is correct
7 Correct 730 ms 7492 KB Output is correct
8 Correct 1535 ms 5044 KB Output is correct
9 Correct 2569 ms 6532 KB Output is correct
10 Correct 1535 ms 8216 KB Output is correct
11 Correct 2278 ms 5376 KB Output is correct
12 Correct 374 ms 7904 KB Output is correct
13 Correct 1977 ms 7436 KB Output is correct
14 Correct 2501 ms 6448 KB Output is correct
15 Correct 678 ms 8940 KB Output is correct
16 Correct 1855 ms 7860 KB Output is correct
17 Correct 1554 ms 5708 KB Output is correct
18 Correct 1534 ms 5664 KB Output is correct
19 Correct 1592 ms 5788 KB Output is correct
20 Correct 1527 ms 5700 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1840 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 9 ms 2040 KB Output is correct
5 Correct 17 ms 2128 KB Output is correct
6 Correct 21 ms 2044 KB Output is correct
7 Correct 38 ms 2036 KB Output is correct
8 Correct 57 ms 2148 KB Output is correct
9 Correct 60 ms 2140 KB Output is correct
10 Correct 26 ms 2168 KB Output is correct
11 Correct 32 ms 2040 KB Output is correct
12 Correct 33 ms 2040 KB Output is correct
13 Correct 26 ms 2168 KB Output is correct
14 Correct 67 ms 2040 KB Output is correct
15 Correct 9 ms 1912 KB Output is correct
16 Correct 12 ms 2040 KB Output is correct
17 Correct 70 ms 2076 KB Output is correct
18 Correct 41 ms 2040 KB Output is correct
19 Correct 66 ms 2088 KB Output is correct
20 Correct 63 ms 2168 KB Output is correct
21 Correct 1532 ms 4748 KB Output is correct
22 Correct 1521 ms 5592 KB Output is correct
23 Correct 1504 ms 5808 KB Output is correct
24 Correct 1452 ms 5808 KB Output is correct
25 Correct 326 ms 7040 KB Output is correct
26 Correct 221 ms 7160 KB Output is correct
27 Correct 1609 ms 5288 KB Output is correct
28 Correct 1515 ms 5464 KB Output is correct
29 Correct 1555 ms 5316 KB Output is correct
30 Correct 1528 ms 4252 KB Output is correct
31 Correct 1652 ms 4372 KB Output is correct
32 Correct 1145 ms 6112 KB Output is correct
33 Correct 179 ms 4188 KB Output is correct
34 Correct 190 ms 4136 KB Output is correct
35 Correct 179 ms 4056 KB Output is correct
36 Correct 198 ms 4044 KB Output is correct
37 Correct 945 ms 6344 KB Output is correct
38 Correct 1433 ms 4724 KB Output is correct
39 Correct 730 ms 7492 KB Output is correct
40 Correct 1535 ms 5044 KB Output is correct
41 Correct 2569 ms 6532 KB Output is correct
42 Correct 1535 ms 8216 KB Output is correct
43 Correct 2278 ms 5376 KB Output is correct
44 Correct 374 ms 7904 KB Output is correct
45 Correct 1977 ms 7436 KB Output is correct
46 Correct 2501 ms 6448 KB Output is correct
47 Correct 678 ms 8940 KB Output is correct
48 Correct 1855 ms 7860 KB Output is correct
49 Correct 1554 ms 5708 KB Output is correct
50 Correct 1534 ms 5664 KB Output is correct
51 Correct 1592 ms 5788 KB Output is correct
52 Correct 1527 ms 5700 KB Output is correct
53 Correct 208 ms 4516 KB Output is correct
54 Correct 207 ms 4540 KB Output is correct
55 Correct 179 ms 4392 KB Output is correct
56 Correct 185 ms 4468 KB Output is correct
57 Correct 1759 ms 5608 KB Output is correct
58 Correct 1370 ms 4280 KB Output is correct
59 Correct 1328 ms 6264 KB Output is correct
60 Correct 1301 ms 4108 KB Output is correct
61 Correct 2033 ms 7168 KB Output is correct
62 Correct 877 ms 8564 KB Output is correct
63 Correct 510 ms 8848 KB Output is correct
64 Correct 803 ms 8552 KB Output is correct
65 Correct 2386 ms 5492 KB Output is correct
66 Correct 2371 ms 5160 KB Output is correct
67 Correct 1806 ms 7276 KB Output is correct
68 Correct 2309 ms 6676 KB Output is correct
69 Correct 1538 ms 5936 KB Output is correct
70 Correct 1517 ms 5956 KB Output is correct
71 Correct 1553 ms 5880 KB Output is correct
72 Correct 1528 ms 6040 KB Output is correct
73 Correct 2606 ms 5924 KB Output is correct
74 Correct 2383 ms 6688 KB Output is correct
75 Correct 203 ms 7840 KB Output is correct
76 Correct 451 ms 8068 KB Output is correct
77 Correct 196 ms 4524 KB Output is correct
78 Correct 183 ms 4524 KB Output is correct
79 Correct 207 ms 4620 KB Output is correct
80 Correct 192 ms 4568 KB Output is correct
81 Correct 2382 ms 6628 KB Output is correct
82 Correct 2558 ms 5992 KB Output is correct
83 Correct 2194 ms 5280 KB Output is correct
84 Correct 2393 ms 6852 KB Output is correct
85 Correct 1758 ms 7120 KB Output is correct
86 Correct 1664 ms 7736 KB Output is correct
87 Correct 2524 ms 5992 KB Output is correct
88 Correct 2213 ms 4996 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1784 KB Output is correct
2 Correct 3 ms 1840 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 9 ms 2040 KB Output is correct
5 Correct 17 ms 2128 KB Output is correct
6 Correct 21 ms 2044 KB Output is correct
7 Correct 38 ms 2036 KB Output is correct
8 Correct 57 ms 2148 KB Output is correct
9 Correct 60 ms 2140 KB Output is correct
10 Correct 26 ms 2168 KB Output is correct
11 Correct 32 ms 2040 KB Output is correct
12 Correct 33 ms 2040 KB Output is correct
13 Correct 26 ms 2168 KB Output is correct
14 Correct 67 ms 2040 KB Output is correct
15 Correct 9 ms 1912 KB Output is correct
16 Correct 12 ms 2040 KB Output is correct
17 Correct 70 ms 2076 KB Output is correct
18 Correct 41 ms 2040 KB Output is correct
19 Correct 66 ms 2088 KB Output is correct
20 Correct 63 ms 2168 KB Output is correct
21 Correct 1532 ms 4748 KB Output is correct
22 Correct 1521 ms 5592 KB Output is correct
23 Correct 1504 ms 5808 KB Output is correct
24 Correct 1452 ms 5808 KB Output is correct
25 Correct 326 ms 7040 KB Output is correct
26 Correct 221 ms 7160 KB Output is correct
27 Correct 1609 ms 5288 KB Output is correct
28 Correct 1515 ms 5464 KB Output is correct
29 Correct 1555 ms 5316 KB Output is correct
30 Correct 1528 ms 4252 KB Output is correct
31 Correct 1652 ms 4372 KB Output is correct
32 Correct 1145 ms 6112 KB Output is correct
33 Correct 213 ms 3792 KB Output is correct
34 Correct 176 ms 3676 KB Output is correct
35 Correct 318 ms 3700 KB Output is correct
36 Correct 181 ms 3712 KB Output is correct
37 Correct 685 ms 5620 KB Output is correct
38 Correct 887 ms 5124 KB Output is correct
39 Correct 888 ms 5632 KB Output is correct
40 Correct 228 ms 6400 KB Output is correct
41 Correct 560 ms 7512 KB Output is correct
42 Correct 1628 ms 6540 KB Output is correct
43 Correct 1475 ms 3920 KB Output is correct
44 Correct 1547 ms 6868 KB Output is correct
45 Correct 1870 ms 6728 KB Output is correct
46 Correct 2353 ms 5576 KB Output is correct
47 Correct 2334 ms 5332 KB Output is correct
48 Correct 2227 ms 4844 KB Output is correct
49 Correct 1056 ms 5084 KB Output is correct
50 Correct 1047 ms 5252 KB Output is correct
51 Correct 1053 ms 5156 KB Output is correct
52 Correct 1052 ms 5284 KB Output is correct
53 Correct 1560 ms 4488 KB Output is correct
54 Correct 2386 ms 5764 KB Output is correct
55 Correct 2146 ms 6160 KB Output is correct
56 Correct 2413 ms 5944 KB Output is correct
57 Correct 231 ms 4404 KB Output is correct
58 Correct 187 ms 4420 KB Output is correct
59 Correct 214 ms 4240 KB Output is correct
60 Correct 195 ms 4404 KB Output is correct
61 Correct 2053 ms 6752 KB Output is correct
62 Correct 2025 ms 6768 KB Output is correct
63 Correct 524 ms 8396 KB Output is correct
64 Correct 1637 ms 7404 KB Output is correct
65 Correct 1803 ms 7016 KB Output is correct
66 Correct 2388 ms 5676 KB Output is correct
67 Correct 2127 ms 6516 KB Output is correct
68 Correct 1627 ms 7472 KB Output is correct
69 Correct 179 ms 4188 KB Output is correct
70 Correct 190 ms 4136 KB Output is correct
71 Correct 179 ms 4056 KB Output is correct
72 Correct 198 ms 4044 KB Output is correct
73 Correct 945 ms 6344 KB Output is correct
74 Correct 1433 ms 4724 KB Output is correct
75 Correct 730 ms 7492 KB Output is correct
76 Correct 1535 ms 5044 KB Output is correct
77 Correct 2569 ms 6532 KB Output is correct
78 Correct 1535 ms 8216 KB Output is correct
79 Correct 2278 ms 5376 KB Output is correct
80 Correct 374 ms 7904 KB Output is correct
81 Correct 1977 ms 7436 KB Output is correct
82 Correct 2501 ms 6448 KB Output is correct
83 Correct 678 ms 8940 KB Output is correct
84 Correct 1855 ms 7860 KB Output is correct
85 Correct 1554 ms 5708 KB Output is correct
86 Correct 1534 ms 5664 KB Output is correct
87 Correct 1592 ms 5788 KB Output is correct
88 Correct 1527 ms 5700 KB Output is correct
89 Correct 208 ms 4516 KB Output is correct
90 Correct 207 ms 4540 KB Output is correct
91 Correct 179 ms 4392 KB Output is correct
92 Correct 185 ms 4468 KB Output is correct
93 Correct 1759 ms 5608 KB Output is correct
94 Correct 1370 ms 4280 KB Output is correct
95 Correct 1328 ms 6264 KB Output is correct
96 Correct 1301 ms 4108 KB Output is correct
97 Correct 2033 ms 7168 KB Output is correct
98 Correct 877 ms 8564 KB Output is correct
99 Correct 510 ms 8848 KB Output is correct
100 Correct 803 ms 8552 KB Output is correct
101 Correct 2386 ms 5492 KB Output is correct
102 Correct 2371 ms 5160 KB Output is correct
103 Correct 1806 ms 7276 KB Output is correct
104 Correct 2309 ms 6676 KB Output is correct
105 Correct 1538 ms 5936 KB Output is correct
106 Correct 1517 ms 5956 KB Output is correct
107 Correct 1553 ms 5880 KB Output is correct
108 Correct 1528 ms 6040 KB Output is correct
109 Correct 2606 ms 5924 KB Output is correct
110 Correct 2383 ms 6688 KB Output is correct
111 Correct 203 ms 7840 KB Output is correct
112 Correct 451 ms 8068 KB Output is correct
113 Correct 196 ms 4524 KB Output is correct
114 Correct 183 ms 4524 KB Output is correct
115 Correct 207 ms 4620 KB Output is correct
116 Correct 192 ms 4568 KB Output is correct
117 Correct 2382 ms 6628 KB Output is correct
118 Correct 2558 ms 5992 KB Output is correct
119 Correct 2194 ms 5280 KB Output is correct
120 Correct 2393 ms 6852 KB Output is correct
121 Correct 1758 ms 7120 KB Output is correct
122 Correct 1664 ms 7736 KB Output is correct
123 Correct 2524 ms 5992 KB Output is correct
124 Correct 2213 ms 4996 KB Output is correct
125 Correct 447 ms 6980 KB Output is correct
126 Correct 482 ms 6908 KB Output is correct
127 Correct 626 ms 7012 KB Output is correct
128 Correct 503 ms 6904 KB Output is correct
129 Correct 427 ms 7000 KB Output is correct
130 Correct 544 ms 7028 KB Output is correct
131 Correct 3533 ms 6244 KB Output is correct
132 Correct 4483 ms 8996 KB Output is correct
133 Correct 3566 ms 13480 KB Output is correct
134 Correct 4125 ms 10236 KB Output is correct
135 Correct 3227 ms 13804 KB Output is correct
136 Correct 2396 ms 9200 KB Output is correct
137 Correct 1876 ms 17364 KB Output is correct
138 Execution timed out 5063 ms 14340 KB Time limit exceeded
139 Halted 0 ms 0 KB -