oj.uz

Submission #161346

# Submission time Handle Problem Language Result Execution time Memory
161346 2019-11-01T21:24:59 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 17448 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;
const ll block = 315;
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 2 ms 1980 KB Output is correct
2 Correct 4 ms 1932 KB Output is correct
3 Correct 10 ms 2168 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 15 ms 2296 KB Output is correct
6 Correct 17 ms 2296 KB Output is correct
7 Correct 42 ms 2196 KB Output is correct
8 Correct 39 ms 2236 KB Output is correct
9 Correct 42 ms 2296 KB Output is correct
10 Correct 19 ms 2296 KB Output is correct
11 Correct 25 ms 2252 KB Output is correct
12 Correct 25 ms 2168 KB Output is correct
13 Correct 19 ms 2296 KB Output is correct
14 Correct 48 ms 2296 KB Output is correct
15 Correct 9 ms 2168 KB Output is correct
16 Correct 10 ms 2168 KB Output is correct
17 Correct 48 ms 2208 KB Output is correct
18 Correct 27 ms 2292 KB Output is correct
19 Correct 49 ms 2224 KB Output is correct
20 Correct 44 ms 2196 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 6344 KB Output is correct
2 Correct 1494 ms 6308 KB Output is correct
3 Correct 1472 ms 6356 KB Output is correct
4 Correct 1449 ms 6612 KB Output is correct
5 Correct 368 ms 8092 KB Output is correct
6 Correct 232 ms 8156 KB Output is correct
7 Correct 1501 ms 6328 KB Output is correct
8 Correct 1510 ms 6304 KB Output is correct
9 Correct 1484 ms 4616 KB Output is correct
10 Correct 1538 ms 3392 KB Output is correct
11 Correct 1452 ms 3584 KB Output is correct
12 Correct 1162 ms 5480 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 3576 KB Output is correct
2 Correct 168 ms 3548 KB Output is correct
3 Correct 304 ms 3556 KB Output is correct
4 Correct 172 ms 3576 KB Output is correct
5 Correct 566 ms 5580 KB Output is correct
6 Correct 734 ms 4880 KB Output is correct
7 Correct 647 ms 5260 KB Output is correct
8 Correct 213 ms 6300 KB Output is correct
9 Correct 503 ms 7596 KB Output is correct
10 Correct 1247 ms 6424 KB Output is correct
11 Correct 877 ms 3888 KB Output is correct
12 Correct 1412 ms 6692 KB Output is correct
13 Correct 1396 ms 6136 KB Output is correct
14 Correct 1669 ms 5044 KB Output is correct
15 Correct 1630 ms 4824 KB Output is correct
16 Correct 1533 ms 4284 KB Output is correct
17 Correct 800 ms 4572 KB Output is correct
18 Correct 822 ms 4556 KB Output is correct
19 Correct 860 ms 4464 KB Output is correct
20 Correct 799 ms 4548 KB Output is correct
21 Correct 1038 ms 3932 KB Output is correct
22 Correct 1685 ms 5148 KB Output is correct
23 Correct 1597 ms 5848 KB Output is correct
24 Correct 1690 ms 5212 KB Output is correct
25 Correct 216 ms 3556 KB Output is correct
26 Correct 181 ms 3520 KB Output is correct
27 Correct 215 ms 3540 KB Output is correct
28 Correct 190 ms 3696 KB Output is correct
29 Correct 1555 ms 6132 KB Output is correct
30 Correct 1499 ms 5908 KB Output is correct
31 Correct 440 ms 7648 KB Output is correct
32 Correct 1276 ms 6304 KB Output is correct
33 Correct 1352 ms 6228 KB Output is correct
34 Correct 1617 ms 4676 KB Output is correct
35 Correct 1588 ms 5544 KB Output is correct
36 Correct 1270 ms 6648 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 3576 KB Output is correct
2 Correct 180 ms 3560 KB Output is correct
3 Correct 176 ms 3624 KB Output is correct
4 Correct 193 ms 3564 KB Output is correct
5 Correct 965 ms 5876 KB Output is correct
6 Correct 1148 ms 3204 KB Output is correct
7 Correct 770 ms 6128 KB Output is correct
8 Correct 1336 ms 3404 KB Output is correct
9 Correct 1980 ms 5212 KB Output is correct
10 Correct 1284 ms 6964 KB Output is correct
11 Correct 1570 ms 4304 KB Output is correct
12 Correct 322 ms 7740 KB Output is correct
13 Correct 1702 ms 6240 KB Output is correct
14 Correct 1833 ms 5184 KB Output is correct
15 Correct 569 ms 7676 KB Output is correct
16 Correct 1462 ms 6448 KB Output is correct
17 Correct 1495 ms 4616 KB Output is correct
18 Correct 1506 ms 4892 KB Output is correct
19 Correct 1491 ms 4924 KB Output is correct
20 Correct 1593 ms 4852 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1980 KB Output is correct
2 Correct 4 ms 1932 KB Output is correct
3 Correct 10 ms 2168 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 15 ms 2296 KB Output is correct
6 Correct 17 ms 2296 KB Output is correct
7 Correct 42 ms 2196 KB Output is correct
8 Correct 39 ms 2236 KB Output is correct
9 Correct 42 ms 2296 KB Output is correct
10 Correct 19 ms 2296 KB Output is correct
11 Correct 25 ms 2252 KB Output is correct
12 Correct 25 ms 2168 KB Output is correct
13 Correct 19 ms 2296 KB Output is correct
14 Correct 48 ms 2296 KB Output is correct
15 Correct 9 ms 2168 KB Output is correct
16 Correct 10 ms 2168 KB Output is correct
17 Correct 48 ms 2208 KB Output is correct
18 Correct 27 ms 2292 KB Output is correct
19 Correct 49 ms 2224 KB Output is correct
20 Correct 44 ms 2196 KB Output is correct
21 Correct 1510 ms 6344 KB Output is correct
22 Correct 1494 ms 6308 KB Output is correct
23 Correct 1472 ms 6356 KB Output is correct
24 Correct 1449 ms 6612 KB Output is correct
25 Correct 368 ms 8092 KB Output is correct
26 Correct 232 ms 8156 KB Output is correct
27 Correct 1501 ms 6328 KB Output is correct
28 Correct 1510 ms 6304 KB Output is correct
29 Correct 1484 ms 4616 KB Output is correct
30 Correct 1538 ms 3392 KB Output is correct
31 Correct 1452 ms 3584 KB Output is correct
32 Correct 1162 ms 5480 KB Output is correct
33 Correct 304 ms 3576 KB Output is correct
34 Correct 180 ms 3560 KB Output is correct
35 Correct 176 ms 3624 KB Output is correct
36 Correct 193 ms 3564 KB Output is correct
37 Correct 965 ms 5876 KB Output is correct
38 Correct 1148 ms 3204 KB Output is correct
39 Correct 770 ms 6128 KB Output is correct
40 Correct 1336 ms 3404 KB Output is correct
41 Correct 1980 ms 5212 KB Output is correct
42 Correct 1284 ms 6964 KB Output is correct
43 Correct 1570 ms 4304 KB Output is correct
44 Correct 322 ms 7740 KB Output is correct
45 Correct 1702 ms 6240 KB Output is correct
46 Correct 1833 ms 5184 KB Output is correct
47 Correct 569 ms 7676 KB Output is correct
48 Correct 1462 ms 6448 KB Output is correct
49 Correct 1495 ms 4616 KB Output is correct
50 Correct 1506 ms 4892 KB Output is correct
51 Correct 1491 ms 4924 KB Output is correct
52 Correct 1593 ms 4852 KB Output is correct
53 Correct 195 ms 3676 KB Output is correct
54 Correct 204 ms 3628 KB Output is correct
55 Correct 171 ms 3620 KB Output is correct
56 Correct 182 ms 3620 KB Output is correct
57 Correct 1537 ms 4204 KB Output is correct
58 Correct 1004 ms 3188 KB Output is correct
59 Correct 1368 ms 5272 KB Output is correct
60 Correct 1000 ms 3144 KB Output is correct
61 Correct 1713 ms 6400 KB Output is correct
62 Correct 756 ms 7472 KB Output is correct
63 Correct 440 ms 7764 KB Output is correct
64 Correct 689 ms 7472 KB Output is correct
65 Correct 1852 ms 4648 KB Output is correct
66 Correct 1592 ms 4312 KB Output is correct
67 Correct 1433 ms 7112 KB Output is correct
68 Correct 1726 ms 5644 KB Output is correct
69 Correct 1468 ms 4856 KB Output is correct
70 Correct 1509 ms 4840 KB Output is correct
71 Correct 1501 ms 4760 KB Output is correct
72 Correct 1517 ms 4788 KB Output is correct
73 Correct 1852 ms 4872 KB Output is correct
74 Correct 1898 ms 5780 KB Output is correct
75 Correct 203 ms 6960 KB Output is correct
76 Correct 410 ms 7868 KB Output is correct
77 Correct 188 ms 3632 KB Output is correct
78 Correct 178 ms 3592 KB Output is correct
79 Correct 198 ms 3648 KB Output is correct
80 Correct 190 ms 3616 KB Output is correct
81 Correct 1852 ms 5444 KB Output is correct
82 Correct 1841 ms 4980 KB Output is correct
83 Correct 1548 ms 4280 KB Output is correct
84 Correct 1863 ms 5664 KB Output is correct
85 Correct 1445 ms 6740 KB Output is correct
86 Correct 1361 ms 6732 KB Output is correct
87 Correct 1960 ms 5204 KB Output is correct
88 Correct 1492 ms 4144 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1980 KB Output is correct
2 Correct 4 ms 1932 KB Output is correct
3 Correct 10 ms 2168 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 15 ms 2296 KB Output is correct
6 Correct 17 ms 2296 KB Output is correct
7 Correct 42 ms 2196 KB Output is correct
8 Correct 39 ms 2236 KB Output is correct
9 Correct 42 ms 2296 KB Output is correct
10 Correct 19 ms 2296 KB Output is correct
11 Correct 25 ms 2252 KB Output is correct
12 Correct 25 ms 2168 KB Output is correct
13 Correct 19 ms 2296 KB Output is correct
14 Correct 48 ms 2296 KB Output is correct
15 Correct 9 ms 2168 KB Output is correct
16 Correct 10 ms 2168 KB Output is correct
17 Correct 48 ms 2208 KB Output is correct
18 Correct 27 ms 2292 KB Output is correct
19 Correct 49 ms 2224 KB Output is correct
20 Correct 44 ms 2196 KB Output is correct
21 Correct 1510 ms 6344 KB Output is correct
22 Correct 1494 ms 6308 KB Output is correct
23 Correct 1472 ms 6356 KB Output is correct
24 Correct 1449 ms 6612 KB Output is correct
25 Correct 368 ms 8092 KB Output is correct
26 Correct 232 ms 8156 KB Output is correct
27 Correct 1501 ms 6328 KB Output is correct
28 Correct 1510 ms 6304 KB Output is correct
29 Correct 1484 ms 4616 KB Output is correct
30 Correct 1538 ms 3392 KB Output is correct
31 Correct 1452 ms 3584 KB Output is correct
32 Correct 1162 ms 5480 KB Output is correct
33 Correct 210 ms 3576 KB Output is correct
34 Correct 168 ms 3548 KB Output is correct
35 Correct 304 ms 3556 KB Output is correct
36 Correct 172 ms 3576 KB Output is correct
37 Correct 566 ms 5580 KB Output is correct
38 Correct 734 ms 4880 KB Output is correct
39 Correct 647 ms 5260 KB Output is correct
40 Correct 213 ms 6300 KB Output is correct
41 Correct 503 ms 7596 KB Output is correct
42 Correct 1247 ms 6424 KB Output is correct
43 Correct 877 ms 3888 KB Output is correct
44 Correct 1412 ms 6692 KB Output is correct
45 Correct 1396 ms 6136 KB Output is correct
46 Correct 1669 ms 5044 KB Output is correct
47 Correct 1630 ms 4824 KB Output is correct
48 Correct 1533 ms 4284 KB Output is correct
49 Correct 800 ms 4572 KB Output is correct
50 Correct 822 ms 4556 KB Output is correct
51 Correct 860 ms 4464 KB Output is correct
52 Correct 799 ms 4548 KB Output is correct
53 Correct 1038 ms 3932 KB Output is correct
54 Correct 1685 ms 5148 KB Output is correct
55 Correct 1597 ms 5848 KB Output is correct
56 Correct 1690 ms 5212 KB Output is correct
57 Correct 216 ms 3556 KB Output is correct
58 Correct 181 ms 3520 KB Output is correct
59 Correct 215 ms 3540 KB Output is correct
60 Correct 190 ms 3696 KB Output is correct
61 Correct 1555 ms 6132 KB Output is correct
62 Correct 1499 ms 5908 KB Output is correct
63 Correct 440 ms 7648 KB Output is correct
64 Correct 1276 ms 6304 KB Output is correct
65 Correct 1352 ms 6228 KB Output is correct
66 Correct 1617 ms 4676 KB Output is correct
67 Correct 1588 ms 5544 KB Output is correct
68 Correct 1270 ms 6648 KB Output is correct
69 Correct 304 ms 3576 KB Output is correct
70 Correct 180 ms 3560 KB Output is correct
71 Correct 176 ms 3624 KB Output is correct
72 Correct 193 ms 3564 KB Output is correct
73 Correct 965 ms 5876 KB Output is correct
74 Correct 1148 ms 3204 KB Output is correct
75 Correct 770 ms 6128 KB Output is correct
76 Correct 1336 ms 3404 KB Output is correct
77 Correct 1980 ms 5212 KB Output is correct
78 Correct 1284 ms 6964 KB Output is correct
79 Correct 1570 ms 4304 KB Output is correct
80 Correct 322 ms 7740 KB Output is correct
81 Correct 1702 ms 6240 KB Output is correct
82 Correct 1833 ms 5184 KB Output is correct
83 Correct 569 ms 7676 KB Output is correct
84 Correct 1462 ms 6448 KB Output is correct
85 Correct 1495 ms 4616 KB Output is correct
86 Correct 1506 ms 4892 KB Output is correct
87 Correct 1491 ms 4924 KB Output is correct
88 Correct 1593 ms 4852 KB Output is correct
89 Correct 195 ms 3676 KB Output is correct
90 Correct 204 ms 3628 KB Output is correct
91 Correct 171 ms 3620 KB Output is correct
92 Correct 182 ms 3620 KB Output is correct
93 Correct 1537 ms 4204 KB Output is correct
94 Correct 1004 ms 3188 KB Output is correct
95 Correct 1368 ms 5272 KB Output is correct
96 Correct 1000 ms 3144 KB Output is correct
97 Correct 1713 ms 6400 KB Output is correct
98 Correct 756 ms 7472 KB Output is correct
99 Correct 440 ms 7764 KB Output is correct
100 Correct 689 ms 7472 KB Output is correct
101 Correct 1852 ms 4648 KB Output is correct
102 Correct 1592 ms 4312 KB Output is correct
103 Correct 1433 ms 7112 KB Output is correct
104 Correct 1726 ms 5644 KB Output is correct
105 Correct 1468 ms 4856 KB Output is correct
106 Correct 1509 ms 4840 KB Output is correct
107 Correct 1501 ms 4760 KB Output is correct
108 Correct 1517 ms 4788 KB Output is correct
109 Correct 1852 ms 4872 KB Output is correct
110 Correct 1898 ms 5780 KB Output is correct
111 Correct 203 ms 6960 KB Output is correct
112 Correct 410 ms 7868 KB Output is correct
113 Correct 188 ms 3632 KB Output is correct
114 Correct 178 ms 3592 KB Output is correct
115 Correct 198 ms 3648 KB Output is correct
116 Correct 190 ms 3616 KB Output is correct
117 Correct 1852 ms 5444 KB Output is correct
118 Correct 1841 ms 4980 KB Output is correct
119 Correct 1548 ms 4280 KB Output is correct
120 Correct 1863 ms 5664 KB Output is correct
121 Correct 1445 ms 6740 KB Output is correct
122 Correct 1361 ms 6732 KB Output is correct
123 Correct 1960 ms 5204 KB Output is correct
124 Correct 1492 ms 4144 KB Output is correct
125 Correct 471 ms 5984 KB Output is correct
126 Correct 509 ms 6260 KB Output is correct
127 Correct 661 ms 6828 KB Output is correct
128 Correct 523 ms 6828 KB Output is correct
129 Correct 471 ms 6656 KB Output is correct
130 Correct 565 ms 6804 KB Output is correct
131 Correct 3028 ms 5436 KB Output is correct
132 Correct 4864 ms 8064 KB Output is correct
133 Correct 4075 ms 8596 KB Output is correct
134 Correct 3733 ms 4412 KB Output is correct
135 Correct 3770 ms 8880 KB Output is correct
136 Correct 1676 ms 3200 KB Output is correct
137 Correct 1862 ms 13068 KB Output is correct
138 Correct 4924 ms 9920 KB Output is correct
139 Correct 3740 ms 11708 KB Output is correct
140 Correct 2594 ms 12724 KB Output is correct
141 Correct 4446 ms 10636 KB Output is correct
142 Correct 2866 ms 5904 KB Output is correct
143 Correct 4318 ms 7652 KB Output is correct
144 Correct 2054 ms 6588 KB Output is correct
145 Correct 2443 ms 13588 KB Output is correct
146 Correct 4915 ms 8980 KB Output is correct
147 Correct 4452 ms 11044 KB Output is correct
148 Correct 4258 ms 11396 KB Output is correct
149 Correct 4763 ms 12344 KB Output is correct
150 Correct 4776 ms 12540 KB Output is correct
151 Correct 4773 ms 12640 KB Output is correct
152 Correct 4797 ms 12484 KB Output is correct
153 Correct 4917 ms 12516 KB Output is correct
154 Correct 4845 ms 12660 KB Output is correct
155 Correct 3713 ms 10460 KB Output is correct
156 Correct 4876 ms 11196 KB Output is correct
157 Correct 2493 ms 17056 KB Output is correct
158 Correct 2082 ms 17448 KB Output is correct
159 Correct 4800 ms 14564 KB Output is correct
160 Execution timed out 5079 ms 12472 KB Time limit exceeded
161 Halted 0 ms 0 KB -