oj.uz

답안 #161331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161331 2019-11-01T20:35:25 Z pink_bittern Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 6964 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 = 100;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 10 ms 1276 KB Output is correct
4 Correct 10 ms 1272 KB Output is correct
5 Correct 23 ms 1656 KB Output is correct
6 Correct 28 ms 1400 KB Output is correct
7 Correct 41 ms 1400 KB Output is correct
8 Correct 90 ms 1400 KB Output is correct
9 Correct 120 ms 1528 KB Output is correct
10 Correct 41 ms 1576 KB Output is correct
11 Correct 45 ms 1400 KB Output is correct
12 Correct 44 ms 1400 KB Output is correct
13 Correct 43 ms 1656 KB Output is correct
14 Correct 113 ms 1476 KB Output is correct
15 Correct 10 ms 1272 KB Output is correct
16 Correct 13 ms 1272 KB Output is correct
17 Correct 59 ms 1400 KB Output is correct
18 Correct 83 ms 1404 KB Output is correct
19 Correct 66 ms 1448 KB Output is correct
20 Correct 71 ms 1372 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1979 ms 4164 KB Output is correct
2 Correct 1895 ms 4100 KB Output is correct
3 Correct 1911 ms 4136 KB Output is correct
4 Correct 1766 ms 4396 KB Output is correct
5 Correct 354 ms 5880 KB Output is correct
6 Correct 231 ms 6132 KB Output is correct
7 Correct 1914 ms 4244 KB Output is correct
8 Correct 2099 ms 4292 KB Output is correct
9 Correct 2036 ms 4324 KB Output is correct
10 Correct 2165 ms 2848 KB Output is correct
11 Correct 2230 ms 3164 KB Output is correct
12 Correct 1322 ms 5476 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 3168 KB Output is correct
2 Correct 208 ms 3152 KB Output is correct
3 Correct 330 ms 3220 KB Output is correct
4 Correct 211 ms 3176 KB Output is correct
5 Correct 972 ms 5444 KB Output is correct
6 Correct 1296 ms 4916 KB Output is correct
7 Correct 1142 ms 5212 KB Output is correct
8 Correct 354 ms 6160 KB Output is correct
9 Correct 1106 ms 6560 KB Output is correct
10 Correct 2804 ms 6228 KB Output is correct
11 Correct 2187 ms 3440 KB Output is correct
12 Correct 2703 ms 6436 KB Output is correct
13 Correct 3306 ms 5852 KB Output is correct
14 Correct 4347 ms 4360 KB Output is correct
15 Correct 4422 ms 4264 KB Output is correct
16 Correct 4099 ms 3812 KB Output is correct
17 Correct 1529 ms 4024 KB Output is correct
18 Correct 1702 ms 4080 KB Output is correct
19 Correct 1620 ms 4084 KB Output is correct
20 Correct 1766 ms 3992 KB Output is correct
21 Correct 2735 ms 3108 KB Output is correct
22 Correct 4363 ms 4612 KB Output is correct
23 Correct 3878 ms 5112 KB Output is correct
24 Correct 4341 ms 4548 KB Output is correct
25 Correct 269 ms 2572 KB Output is correct
26 Correct 220 ms 2484 KB Output is correct
27 Correct 245 ms 2528 KB Output is correct
28 Correct 231 ms 2484 KB Output is correct
29 Correct 3503 ms 5300 KB Output is correct
30 Correct 3514 ms 5220 KB Output is correct
31 Correct 852 ms 6024 KB Output is correct
32 Correct 2809 ms 5708 KB Output is correct
33 Correct 3126 ms 5840 KB Output is correct
34 Correct 4416 ms 4068 KB Output is correct
35 Correct 3743 ms 4852 KB Output is correct
36 Correct 2901 ms 5896 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 2656 KB Output is correct
2 Correct 211 ms 2672 KB Output is correct
3 Correct 220 ms 2512 KB Output is correct
4 Correct 233 ms 2580 KB Output is correct
5 Correct 1079 ms 5168 KB Output is correct
6 Correct 2102 ms 2312 KB Output is correct
7 Correct 809 ms 5352 KB Output is correct
8 Correct 2227 ms 2544 KB Output is correct
9 Correct 4604 ms 4312 KB Output is correct
10 Correct 2528 ms 6244 KB Output is correct
11 Correct 4048 ms 3464 KB Output is correct
12 Correct 533 ms 5788 KB Output is correct
13 Correct 3400 ms 5624 KB Output is correct
14 Correct 4545 ms 4372 KB Output is correct
15 Correct 1029 ms 5960 KB Output is correct
16 Correct 3107 ms 5780 KB Output is correct
17 Correct 1909 ms 3876 KB Output is correct
18 Correct 1880 ms 3844 KB Output is correct
19 Correct 1890 ms 3828 KB Output is correct
20 Correct 1919 ms 3828 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 10 ms 1276 KB Output is correct
4 Correct 10 ms 1272 KB Output is correct
5 Correct 23 ms 1656 KB Output is correct
6 Correct 28 ms 1400 KB Output is correct
7 Correct 41 ms 1400 KB Output is correct
8 Correct 90 ms 1400 KB Output is correct
9 Correct 120 ms 1528 KB Output is correct
10 Correct 41 ms 1576 KB Output is correct
11 Correct 45 ms 1400 KB Output is correct
12 Correct 44 ms 1400 KB Output is correct
13 Correct 43 ms 1656 KB Output is correct
14 Correct 113 ms 1476 KB Output is correct
15 Correct 10 ms 1272 KB Output is correct
16 Correct 13 ms 1272 KB Output is correct
17 Correct 59 ms 1400 KB Output is correct
18 Correct 83 ms 1404 KB Output is correct
19 Correct 66 ms 1448 KB Output is correct
20 Correct 71 ms 1372 KB Output is correct
21 Correct 1979 ms 4164 KB Output is correct
22 Correct 1895 ms 4100 KB Output is correct
23 Correct 1911 ms 4136 KB Output is correct
24 Correct 1766 ms 4396 KB Output is correct
25 Correct 354 ms 5880 KB Output is correct
26 Correct 231 ms 6132 KB Output is correct
27 Correct 1914 ms 4244 KB Output is correct
28 Correct 2099 ms 4292 KB Output is correct
29 Correct 2036 ms 4324 KB Output is correct
30 Correct 2165 ms 2848 KB Output is correct
31 Correct 2230 ms 3164 KB Output is correct
32 Correct 1322 ms 5476 KB Output is correct
33 Correct 207 ms 2656 KB Output is correct
34 Correct 211 ms 2672 KB Output is correct
35 Correct 220 ms 2512 KB Output is correct
36 Correct 233 ms 2580 KB Output is correct
37 Correct 1079 ms 5168 KB Output is correct
38 Correct 2102 ms 2312 KB Output is correct
39 Correct 809 ms 5352 KB Output is correct
40 Correct 2227 ms 2544 KB Output is correct
41 Correct 4604 ms 4312 KB Output is correct
42 Correct 2528 ms 6244 KB Output is correct
43 Correct 4048 ms 3464 KB Output is correct
44 Correct 533 ms 5788 KB Output is correct
45 Correct 3400 ms 5624 KB Output is correct
46 Correct 4545 ms 4372 KB Output is correct
47 Correct 1029 ms 5960 KB Output is correct
48 Correct 3107 ms 5780 KB Output is correct
49 Correct 1909 ms 3876 KB Output is correct
50 Correct 1880 ms 3844 KB Output is correct
51 Correct 1890 ms 3828 KB Output is correct
52 Correct 1919 ms 3828 KB Output is correct
53 Correct 233 ms 2600 KB Output is correct
54 Correct 273 ms 2588 KB Output is correct
55 Correct 207 ms 2712 KB Output is correct
56 Correct 213 ms 2572 KB Output is correct
57 Correct 2258 ms 3156 KB Output is correct
58 Correct 1968 ms 2156 KB Output is correct
59 Correct 1607 ms 4208 KB Output is correct
60 Correct 1924 ms 2092 KB Output is correct
61 Correct 3421 ms 6696 KB Output is correct
62 Correct 1326 ms 6964 KB Output is correct
63 Correct 766 ms 5988 KB Output is correct
64 Correct 1377 ms 6768 KB Output is correct
65 Correct 4330 ms 3912 KB Output is correct
66 Correct 4135 ms 3544 KB Output is correct
67 Correct 3017 ms 6020 KB Output is correct
68 Correct 3964 ms 4948 KB Output is correct
69 Correct 1906 ms 3908 KB Output is correct
70 Correct 1935 ms 3932 KB Output is correct
71 Correct 1896 ms 3796 KB Output is correct
72 Correct 1908 ms 3884 KB Output is correct
73 Correct 4626 ms 4124 KB Output is correct
74 Correct 4439 ms 4884 KB Output is correct
75 Correct 295 ms 5860 KB Output is correct
76 Correct 691 ms 6144 KB Output is correct
77 Correct 221 ms 2492 KB Output is correct
78 Correct 212 ms 2580 KB Output is correct
79 Correct 234 ms 2560 KB Output is correct
80 Correct 215 ms 2548 KB Output is correct
81 Correct 4147 ms 4736 KB Output is correct
82 Correct 4569 ms 4028 KB Output is correct
83 Correct 3998 ms 3492 KB Output is correct
84 Correct 4131 ms 4796 KB Output is correct
85 Correct 2982 ms 6012 KB Output is correct
86 Correct 2801 ms 5992 KB Output is correct
87 Correct 4439 ms 4476 KB Output is correct
88 Correct 3904 ms 3396 KB Output is correct

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 10 ms 1276 KB Output is correct
4 Correct 10 ms 1272 KB Output is correct
5 Correct 23 ms 1656 KB Output is correct
6 Correct 28 ms 1400 KB Output is correct
7 Correct 41 ms 1400 KB Output is correct
8 Correct 90 ms 1400 KB Output is correct
9 Correct 120 ms 1528 KB Output is correct
10 Correct 41 ms 1576 KB Output is correct
11 Correct 45 ms 1400 KB Output is correct
12 Correct 44 ms 1400 KB Output is correct
13 Correct 43 ms 1656 KB Output is correct
14 Correct 113 ms 1476 KB Output is correct
15 Correct 10 ms 1272 KB Output is correct
16 Correct 13 ms 1272 KB Output is correct
17 Correct 59 ms 1400 KB Output is correct
18 Correct 83 ms 1404 KB Output is correct
19 Correct 66 ms 1448 KB Output is correct
20 Correct 71 ms 1372 KB Output is correct
21 Correct 1979 ms 4164 KB Output is correct
22 Correct 1895 ms 4100 KB Output is correct
23 Correct 1911 ms 4136 KB Output is correct
24 Correct 1766 ms 4396 KB Output is correct
25 Correct 354 ms 5880 KB Output is correct
26 Correct 231 ms 6132 KB Output is correct
27 Correct 1914 ms 4244 KB Output is correct
28 Correct 2099 ms 4292 KB Output is correct
29 Correct 2036 ms 4324 KB Output is correct
30 Correct 2165 ms 2848 KB Output is correct
31 Correct 2230 ms 3164 KB Output is correct
32 Correct 1322 ms 5476 KB Output is correct
33 Correct 242 ms 3168 KB Output is correct
34 Correct 208 ms 3152 KB Output is correct
35 Correct 330 ms 3220 KB Output is correct
36 Correct 211 ms 3176 KB Output is correct
37 Correct 972 ms 5444 KB Output is correct
38 Correct 1296 ms 4916 KB Output is correct
39 Correct 1142 ms 5212 KB Output is correct
40 Correct 354 ms 6160 KB Output is correct
41 Correct 1106 ms 6560 KB Output is correct
42 Correct 2804 ms 6228 KB Output is correct
43 Correct 2187 ms 3440 KB Output is correct
44 Correct 2703 ms 6436 KB Output is correct
45 Correct 3306 ms 5852 KB Output is correct
46 Correct 4347 ms 4360 KB Output is correct
47 Correct 4422 ms 4264 KB Output is correct
48 Correct 4099 ms 3812 KB Output is correct
49 Correct 1529 ms 4024 KB Output is correct
50 Correct 1702 ms 4080 KB Output is correct
51 Correct 1620 ms 4084 KB Output is correct
52 Correct 1766 ms 3992 KB Output is correct
53 Correct 2735 ms 3108 KB Output is correct
54 Correct 4363 ms 4612 KB Output is correct
55 Correct 3878 ms 5112 KB Output is correct
56 Correct 4341 ms 4548 KB Output is correct
57 Correct 269 ms 2572 KB Output is correct
58 Correct 220 ms 2484 KB Output is correct
59 Correct 245 ms 2528 KB Output is correct
60 Correct 231 ms 2484 KB Output is correct
61 Correct 3503 ms 5300 KB Output is correct
62 Correct 3514 ms 5220 KB Output is correct
63 Correct 852 ms 6024 KB Output is correct
64 Correct 2809 ms 5708 KB Output is correct
65 Correct 3126 ms 5840 KB Output is correct
66 Correct 4416 ms 4068 KB Output is correct
67 Correct 3743 ms 4852 KB Output is correct
68 Correct 2901 ms 5896 KB Output is correct
69 Correct 207 ms 2656 KB Output is correct
70 Correct 211 ms 2672 KB Output is correct
71 Correct 220 ms 2512 KB Output is correct
72 Correct 233 ms 2580 KB Output is correct
73 Correct 1079 ms 5168 KB Output is correct
74 Correct 2102 ms 2312 KB Output is correct
75 Correct 809 ms 5352 KB Output is correct
76 Correct 2227 ms 2544 KB Output is correct
77 Correct 4604 ms 4312 KB Output is correct
78 Correct 2528 ms 6244 KB Output is correct
79 Correct 4048 ms 3464 KB Output is correct
80 Correct 533 ms 5788 KB Output is correct
81 Correct 3400 ms 5624 KB Output is correct
82 Correct 4545 ms 4372 KB Output is correct
83 Correct 1029 ms 5960 KB Output is correct
84 Correct 3107 ms 5780 KB Output is correct
85 Correct 1909 ms 3876 KB Output is correct
86 Correct 1880 ms 3844 KB Output is correct
87 Correct 1890 ms 3828 KB Output is correct
88 Correct 1919 ms 3828 KB Output is correct
89 Correct 233 ms 2600 KB Output is correct
90 Correct 273 ms 2588 KB Output is correct
91 Correct 207 ms 2712 KB Output is correct
92 Correct 213 ms 2572 KB Output is correct
93 Correct 2258 ms 3156 KB Output is correct
94 Correct 1968 ms 2156 KB Output is correct
95 Correct 1607 ms 4208 KB Output is correct
96 Correct 1924 ms 2092 KB Output is correct
97 Correct 3421 ms 6696 KB Output is correct
98 Correct 1326 ms 6964 KB Output is correct
99 Correct 766 ms 5988 KB Output is correct
100 Correct 1377 ms 6768 KB Output is correct
101 Correct 4330 ms 3912 KB Output is correct
102 Correct 4135 ms 3544 KB Output is correct
103 Correct 3017 ms 6020 KB Output is correct
104 Correct 3964 ms 4948 KB Output is correct
105 Correct 1906 ms 3908 KB Output is correct
106 Correct 1935 ms 3932 KB Output is correct
107 Correct 1896 ms 3796 KB Output is correct
108 Correct 1908 ms 3884 KB Output is correct
109 Correct 4626 ms 4124 KB Output is correct
110 Correct 4439 ms 4884 KB Output is correct
111 Correct 295 ms 5860 KB Output is correct
112 Correct 691 ms 6144 KB Output is correct
113 Correct 221 ms 2492 KB Output is correct
114 Correct 212 ms 2580 KB Output is correct
115 Correct 234 ms 2560 KB Output is correct
116 Correct 215 ms 2548 KB Output is correct
117 Correct 4147 ms 4736 KB Output is correct
118 Correct 4569 ms 4028 KB Output is correct
119 Correct 3998 ms 3492 KB Output is correct
120 Correct 4131 ms 4796 KB Output is correct
121 Correct 2982 ms 6012 KB Output is correct
122 Correct 2801 ms 5992 KB Output is correct
123 Correct 4439 ms 4476 KB Output is correct
124 Correct 3904 ms 3396 KB Output is correct
125 Correct 503 ms 4468 KB Output is correct
126 Correct 548 ms 4452 KB Output is correct
127 Correct 715 ms 4476 KB Output is correct
128 Correct 537 ms 4500 KB Output is correct
129 Correct 474 ms 4448 KB Output is correct
130 Correct 581 ms 4652 KB Output is correct
131 Correct 4885 ms 3124 KB Output is correct
132 Execution timed out 5096 ms 6124 KB Time limit exceeded
133 Halted 0 ms 0 KB -