QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520943#4371. Spin DoctormshcherbaAC ✓266ms21276kbC++204.9kb2024-08-15 17:49:502024-08-15 17:49:50

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 17:49:50]
  • 评测
  • 测评结果:AC
  • 用时:266ms
  • 内存:21276kb
  • [2024-08-15 17:49:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

struct Pt
{
	int x, y;
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
};

LL sq(const Pt& p)
{
	return (LL)p.x * p.x + (LL)p.y * p.y;
}

int sgn(LL x)
{
	return (0 < x) - (x < 0);
}

LL dot(const Pt& p, const Pt& q)
{
	return (LL)p.x * q.x + (LL)p.y * q.y;
}

LL cross(const Pt& p, const Pt& q)
{
	return (LL)p.x * q.y - (LL)p.y * q.x;
}

LL orient(const Pt& p, const Pt& q, const Pt& r)
{
	return cross(q - p, r - p);
}

bool half(const Pt& p)
{
	assert(sgn(p.x) != 0 || sgn(p.y) != 0);
	return sgn(p.y) == -1 ||
		(sgn(p.y) == 0 && sgn(p.x) == -1);
}

void polarSortAround(const Pt& o, vector<pair<Pt, int>>& v)
{
	sort(ALL(v), [o](pair<Pt, int> pp, pair<Pt, int> qq)
	{
		Pt p = pp.F - o;
		Pt q = qq.F - o;
		bool hp = half(p), hq = half(q);
		if (hp != hq)
			return hp < hq;
		int s = sgn(cross(p, q));
		if (s != 0)
			return s == 1;
		return sq(p) < sq(q);
	});
}

bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
	return sgn(dot(a - p, b - p)) <= 0;
}

bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
	return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}

bool inConvexPolygon(const vector<Pt>& v, const Pt& a)
{
	assert(SZ(v) >= 2);
	if (SZ(v) == 2)
		return onSegment(v[0], v[1], a);
	if (sgn(orient(v.back(), v[0], a)) < 0
		|| sgn(orient(v[0], v[1], a)) < 0)
		return false;
	int i = lower_bound(v.begin() + 2, v.end(), a,
		[&](const Pt& p, const Pt& q)
		{
			return sgn(orient(v[0], p, q)) > 0;
		}) - v.begin();
	return sgn(orient(v[i - 1], v[i], a)) >= 0;
}

vector<Pt> convexHull(vector<Pt> v)
{
	if (SZ(v) <= 1)
		return v;
	sort(ALL(v), [](const Pt& p, const Pt& q)
	{
		int dx = sgn(p.x - q.x);
		if (dx != 0)
			return dx < 0;
		return sgn(p.y - q.y) < 0;
	});
	vector<Pt> lower, upper;
	for (const Pt& p : v)
	{
		while (SZ(lower) > 1
			&& sgn(orient(lower[SZ(lower) - 2], lower.back(), p)) <= 0)
			lower.pop_back();
		while (SZ(upper) > 1
			&& sgn(orient(upper[SZ(upper) - 2], upper.back(), p)) >= 0)
			upper.pop_back();
		lower.PB(p);
		upper.PB(p);
	}
	reverse(ALL(upper));
	lower.insert(lower.end(), next(upper.begin()), prev(upper.end()));
	return lower;
}

PII tangetsToConvexPolygon(const vector<Pt>& v, const Pt& p)
{
	int n = SZ(v), i = 0;
	if (n == 2)
		return {0, 1};
	while (sgn(orient(p, v[i], v[(i + 1) % n]))
		* sgn(orient(p, v[i], v[(i + n - 1) % n])) > 0)
		i++;
	int s1 = 1, s2 = -1;
	if (sgn(orient(p, v[i], v[(i + 1) % n])) == s1
		|| sgn(orient(p, v[i], v[(i + n - 1) % n])) == s2)
		swap(s1, s2);
	PII res;
	int l = i, r = i + n - 1;
	while (r - l > 1)
	{
		int m = (l + r) / 2;
		if (sgn(orient(p, v[i], v[m % n])) != s1
			&& sgn(orient(p, v[m % n], v[(m + 1) % n])) != s1)
			l = m;
		else
			r = m;
	}
	res.F = r % n;
	l = i;
	r = i + n - 1;
	while (r - l > 1)
	{
		int m = (l + r) / 2;
		if (sgn(orient(p, v[i], v[m % n])) == s2
			|| sgn(orient(p, v[m % n], v[(m + 1) % n])) != s2)
			l = m;
		else
			r = m;
	}
	res.S = r % n;
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Pt> v[2];
	FOR(i, 0, n)
	{
		Pt p;
		int c;
		cin >> p.x >> p.y >> c;
		v[c].PB(p);
	}
	vector<Pt> hull = convexHull(v[1]);
	if (SZ(hull) == 1)
	{
		int ans = SZ(v[1]);
		if (ans == 1)
		{
			cout << "1\n";
			return 0;
		}
		for (const Pt& p : v[0])
		{
			if (p.x == hull[0].x && p.y == hull[0].y)
				ans++;
		}
		cout << ans << "\n";
		return 0;
	}
	int cntFalseInside = 0;
	vector<pair<Pt, int>> events;
	int cur = 0;
	for (const Pt& p : v[0])
	{
		if (inConvexPolygon(hull, p))
			cntFalseInside++;
		else
		{
			auto [i1, i2] = tangetsToConvexPolygon(hull, p);
			// assert(sgn(orient(p, hull[i1], hull[i2])) != 0);
			if (sgn(orient(p, hull[i1], hull[i2])) < 0)
				swap(i1, i2);
			events.PB({hull[i1] - p, 1});
			events.PB({hull[i2] - p, -1});
			events.PB({p - hull[i1], 1});
			events.PB({p - hull[i2], -1});
			if ((hull[i1] - p).y <= 0 && (hull[i2] - p).y >= 0)
				cur++;
			else if ((p - hull[i1]).y <= 0 && (p - hull[i2]).y >= 0)
				cur++;
		}
	}
	polarSortAround({0, 0}, events);
	int ans = cur;
	for (int i = 0; i < SZ(events); )
	{
		int j = i;
		while (j < SZ(events) && sgn(cross(events[i].F, events[j].F)) == 0 && sgn(dot(events[i].F, events[j].F)) > 0)
		{
			if (!(events[j].F.x > 0 && events[j].F.y == 0 && events[j].S == 1))
				cur += events[j].S;
			j++;
		}
		ans = min(ans, cur);
		i = j;		
	}
	cout << ans + SZ(v[1]) + cntFalseInside << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3656kb

input:

6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1

output:

8

result:

ok single line: '8'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

100
7487 4751 1
7499 5064 1
7471 5376 1
7404 5683 1
7300 5979 1
7159 6260 1
6984 6520 1
6777 6757 1
6543 6966 1
6284 7144 1
6006 7288 1
5711 7396 1
5405 7466 1
5092 7498 1
4780 7490 1
4469 7442 1
4167 7357 1
3878 7234 1
3607 7075 1
3358 6884 1
3135 6664 1
2941 6417 1
2780 6147 1
2653 5860 1
2564 555...

output:

61

result:

ok single line: '61'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

200
7489 1285 0
6851 8471 0
6122 2766 1
2413 9338 0
1725 7382 0
6984 6520 1
5080 8417 0
2604 5711 1
5833 2643 1
48 2810 0
5316 2439 0
900 7419 0
6809 867 0
6006 7288 1
5092 7498 1
5531 2558 1
7075 6393 1
9979 9313 0
7436 4441 1
4595 2534 1
2598 909 0
842 284 0
3358 6884 1
6522 7976 0
604 5833 0
3607...

output:

125

result:

ok single line: '125'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

300
2253 823 1
1865 9556 0
306 6720 1
8588 1519 1
2756 9468 1
5810 9933 1
1625 9138 0
27 932 0
8124 1097 1
8699 8363 1
7202 9489 1
9420 7337 1
9862 6164 1
908 2128 1
9341 2521 1
372 8140 0
9318 7520 1
1760 34 0
785 612 0
1445 1442 0
9694 3280 1
9496 2152 0
9249 1891 0
2162 9828 0
580 2663 1
1269 832...

output:

234

result:

ok single line: '234'

Test #7:

score: 0
Accepted
time: 60ms
memory: 7084kb

input:

100000
7487 4751 1
7487 4751 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4753 1
7487 4753 1
7487 4753 1
7487 4754 1
7487 4754 1
7487 4754 1
7487 4755 1
7487 4755 1
7487 4755 1
7487 4756 1
7488 4756 1
7488 4756 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4758 1
7488 4758 1
7488 ...

output:

68833

result:

ok single line: '68833'

Test #8:

score: 0
Accepted
time: 65ms
memory: 7052kb

input:

100000
8980 4601 1
8980 4602 1
8980 4602 1
8980 4603 1
8980 4603 1
8980 4604 1
8980 4604 1
8980 4605 1
8980 4605 1
8980 4606 1
8980 4606 1
8980 4607 1
8980 4607 1
8980 4608 1
8980 4608 1
8980 4609 1
8980 4609 1
8980 4610 1
8980 4610 1
8980 4611 1
8981 4611 1
8981 4612 1
8981 4612 1
8981 4613 1
8981 ...

output:

79761

result:

ok single line: '79761'

Test #9:

score: 0
Accepted
time: 60ms
memory: 8576kb

input:

100000
9975 4501 1
9975 4502 1
9975 4503 1
9975 4503 1
9975 4504 1
9975 4504 1
9975 4505 1
9975 4506 1
9975 4506 1
9975 4507 1
9975 4508 1
9975 4508 1
9975 4509 1
9975 4509 1
9975 4510 1
9975 4511 1
9976 4511 1
9976 4512 1
9976 4513 1
9976 4513 1
9976 4514 1
9976 4514 1
9976 4515 1
9976 4516 1
9976 ...

output:

79877

result:

ok single line: '79877'

Test #10:

score: 0
Accepted
time: 72ms
memory: 8320kb

input:

100000
89749 223387 0
295171 424382 0
397151 279092 1
393939 207794 1
109069 198636 1
338201 128673 1
388987 306412 1
401174 201459 0
428943 426416 0
292775 106229 1
181076 383227 1
207577 106125 1
389057 405639 0
358258 146173 1
376103 425370 0
284279 396030 1
342155 368352 1
479748 52614 0
102762 ...

output:

72070

result:

ok single line: '72070'

Test #11:

score: 0
Accepted
time: 66ms
memory: 8500kb

input:

100000
649 24758 0
14496 41252 0
39286 10853 0
19975 37285 1
40085 29490 0
1766 27831 0
5842 586 0
27105 8225 1
11312 32491 1
17523 4856 0
16990 8550 1
4916 12992 0
7696 24913 1
42700 5177 0
43755 27268 0
9922 42370 0
8555 16976 1
17794 36896 0
21532 37468 1
35271 30549 0
31468 10477 1
37030 18776 1...

output:

74280

result:

ok single line: '74280'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
100 100 1
500 500 1
200 200 0

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

5
0 100 0
0 200 1
0 300 0
0 400 1
0 500 0

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

7
100 0 0
200 0 1
300 0 0
400 0 1
500 0 0
600 0 1
700 0 0

output:

5

result:

ok single line: '5'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5
0 0 1
100 100 1
50 50 0
50 25 0
25 50 0

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

2
0 0 1
0 0 0

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2
0 0 1
0 1 0

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

5
100 100 1
50 50 0
100 200 0
150 150 0
100 100 0

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 34ms
memory: 5616kb

input:

250000
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964...

output:

250000

result:

ok single line: '250000'

Test #21:

score: 0
Accepted
time: 155ms
memory: 13428kb

input:

250000
8550 5546 1
1572 3657 1
7112 3904 1
4958 6472 1
6621 8971 1
7230 7901 1
1460 4459 1
3076 5535 1
2823 3202 1
4314 6444 1
5323 9275 1
976 6014 1
9105 7435 1
6937 5228 1
6610 5712 1
8099 5810 1
7207 2629 1
9527 3777 1
3790 3671 1
3223 9511 1
922 2799 1
2708 4697 1
5454 9118 1
7530 9036 1
885 429...

output:

203548

result:

ok single line: '203548'

Test #22:

score: 0
Accepted
time: 103ms
memory: 11384kb

input:

100000
6586 9605 1
688 2874 1
8700 7949 1
4623 47 1
378 3451 1
5368 46 1
309 6390 1
9344 2926 1
8645 8012 1
9105 7435 1
6101 204 1
26 5094 1
41 5318 1
3223 9511 1
9691 6390 1
7664 8934 1
7007 9384 1
1637 8315 1
7530 9036 1
119 4206 1
8082 1418 1
4053 158 1
7263 9224 1
6658 429 1
1883 8550 1
5094 997...

output:

63494

result:

ok single line: '63494'

Test #23:

score: 0
Accepted
time: 105ms
memory: 11708kb

input:

100000
42796 30581 1
27459 44131 1
42756 14344 1
44098 17439 1
18059 44290 1
3096 32112 1
29881 1849 1
42046 13114 1
1641 29437 1
12475 41636 1
10539 4777 1
1458 29023 1
25506 359 1
41181 11813 1
17727 810 1
24795 44765 1
31345 2629 1
14436 2195 1
33256 41132 1
2325 30806 1
4517 34129 1
42771 30628 ...

output:

64584

result:

ok single line: '64584'

Test #24:

score: 0
Accepted
time: 266ms
memory: 20164kb

input:

250000
179223 507524 1
1953878 749817 1
1074428 1995760 1
1038476 1261 1
1873442 1414315 1
1997919 1050970 1
1994767 916993 1
1441559 143861 1
1873064 1414930 1
1021459 1999488 1
1999780 991906 1
46502 748785 1
134097 573595 1
1761948 1566969 1
564999 1860407 1
258192 1590279 1
1305866 68863 1
10008...

output:

177485

result:

ok single line: '177485'

Test #25:

score: 0
Accepted
time: 75ms
memory: 11640kb

input:

100000
25413 13041 0
3240 31742 0
40224 14017 0
9635 20131 0
9251 7361 0
24737 13064 0
13794 13768 0
10113 17490 0
13701 38317 0
30220 25996 0
16214 26720 0
18824 6185 0
18437 41476 0
10938 29854 0
37321 19798 0
41255 20820 0
15690 11981 0
7363 14764 0
13435 43392 0
35370 27782 0
37816 15984 0
20974...

output:

1996

result:

ok single line: '1996'

Test #26:

score: 0
Accepted
time: 56ms
memory: 7800kb

input:

100000
42808 16570 0
13470 16294 0
21837 20456 0
27633 44832 1
43204 31337 0
30846 42318 1
5023 279 0
22500 26620 0
25367 7969 0
25659 16149 1
17340 13731 0
38255 24494 1
13912 3828 0
41341 38404 0
5992 15677 0
18686 26358 0
13515 1119 0
33085 856 0
24749 42396 0
42354 36978 1
10881 39037 0
59 20782...

output:

51005

result:

ok single line: '51005'

Test #27:

score: 0
Accepted
time: 50ms
memory: 7716kb

input:

100000
1295 9516 0
44028 7323 0
22333 23362 0
29472 11339 0
43478 3715 0
31422 11315 0
22500 4988 1
22500 26016 1
6290 12990 0
25921 13160 0
17287 2499 0
30987 13164 0
16024 14510 0
36614 1377 0
11390 42489 1
4761 31273 0
26159 5541 0
38317 1908 0
19293 43226 0
40557 33871 0
16510 19308 1
29122 4453...

output:

51027

result:

ok single line: '51027'

Test #28:

score: 0
Accepted
time: 51ms
memory: 8964kb

input:

100000
24808 42282 0
21168 34391 0
6444 786 0
39361 18331 0
15246 38500 0
22271 34860 0
3431 2169 0
37636 43046 0
18143 19155 0
43898 19065 0
26106 36485 0
11957 25354 0
41529 17038 0
4395 40101 0
5213 13660 0
21949 6678 0
13011 4705 0
39046 20188 0
34676 7351 0
29493 231 0
25178 23889 0
15680 7594 ...

output:

51056

result:

ok single line: '51056'

Test #29:

score: 0
Accepted
time: 78ms
memory: 12408kb

input:

100000
35178 7556 0
43543 24751 0
5084 35731 0
16305 36844 0
22500 20264 0
1630 8212 0
11095 211 0
42801 6599 0
37701 2028 0
17070 1280 0
507 42420 0
14316 5603 0
32825 40550 0
32020 4685 0
22500 6619 1
7743 20810 0
32411 1420 0
42622 23150 0
18429 77 0
8623 17599 0
26346 28983 0
6475 19645 0
30712 ...

output:

1982

result:

ok single line: '1982'

Test #30:

score: 0
Accepted
time: 48ms
memory: 7872kb

input:

100000
44615 16896 0
35703 38357 0
4266 10295 1
3924 27703 0
43769 21876 0
376 32019 0
26638 37892 0
1486 43624 0
42332 30447 0
21852 6617 1
20000 23382 0
32297 4803 1
14563 34582 0
7667 22386 0
26562 23139 0
25281 7017 1
24027 29563 0
21471 43979 0
6113 36704 0
10743 28455 0
20694 10227 0
16574 402...

output:

50748

result:

ok single line: '50748'

Test #31:

score: 0
Accepted
time: 97ms
memory: 9036kb

input:

249943
52338 1932288 0
500604 85230 1
421975 541172 0
1220260 1922275 0
782273 1935347 0
1100991 1806280 0
205837 836278 0
314341 849646 0
482026 1814471 0
1006377 1795879 0
457197 1895481 1
612248 1804355 0
831860 7724 1
1975517 1191035 0
1838023 357991 0
1884236 960643 0
1978434 1272346 1
830 1056...

output:

237745

result:

ok single line: '237745'

Test #32:

score: 0
Accepted
time: 64ms
memory: 6836kb

input:

249924
1692009 1277080 0
1701311 1473926 0
1530920 1558948 0
809839 1544501 0
490718 1778464 0
1596606 1610103 0
1048061 322345 0
1093714 303163 0
1230443 1349196 0
85588 499676 1
710370 217252 0
700457 890768 0
1040631 611336 0
1222799 946458 0
1910466 490490 1
1683127 754616 0
876618 906063 0
4071...

output:

249924

result:

ok single line: '249924'

Test #33:

score: 0
Accepted
time: 69ms
memory: 7192kb

input:

249932
1729117 1770539 1
824212 56933 0
1124972 42036 0
13242 1217548 1
423680 121484 1
904678 196033 0
1845017 1617274 0
791653 394425 0
1584751 1586123 0
834207 7501 1
943442 1585395 0
1616144 144360 1
38206 943159 0
1094152 2372 1
475006 1310991 0
1960291 1348769 0
596237 300239 0
822162 866311 0...

output:

248067

result:

ok single line: '248067'

Test #34:

score: 0
Accepted
time: 241ms
memory: 21136kb

input:

249937
81362 1733185 0
1882027 356824 0
1301758 1983247 0
260027 229804 0
1529823 19648 0
558704 63525 1
627065 43140 1
1566709 1998530 0
1251941 1981808 1
1576571 52684 0
378011 1849464 0
53814 1410946 1
1660021 1755217 0
506015 83019 1
1253852 18492 1
328345 85484 0
424148 96850 0
1977974 1339668 ...

output:

193252

result:

ok single line: '193252'

Test #35:

score: 0
Accepted
time: 246ms
memory: 21276kb

input:

249959
184837 244754 0
948395 1933588 0
41827 88177 0
98303 36005 0
1777482 1742549 0
79639 514417 1
147209 233680 0
1634876 1911722 0
75372 133634 0
133448 84504 0
1656795 1938366 0
771498 14745 1
1459618 1930072 1
1678679 1938641 0
1049900 709 1
202162 267646 0
1991953 1856494 0
261064 1761408 1
1...

output:

81371

result:

ok single line: '81371'

Test #36:

score: 0
Accepted
time: 70ms
memory: 7708kb

input:

249910
1603379 1433343 1
164471 1557523 0
1159628 900250 1
1027168 579138 1
1450567 1867094 0
848409 326306 0
307054 1306503 0
695746 157643 1
1346167 1190499 1
1448398 1652741 1
1807909 1359563 0
175434 87592 0
605107 1359561 1
596349 1324954 0
1264020 1661491 1
983071 372870 1
928003 1824439 1
194...

output:

240919

result:

ok single line: '240919'

Test #37:

score: 0
Accepted
time: 113ms
memory: 14248kb

input:

249955
1062923 1830852 1
50817 1529810 0
1276748 1635310 1
161346 294127 1
1067911 1389639 1
89037 577579 0
124090 88710 0
304488 1799140 0
743644 1566242 1
1787471 1881511 0
49861 1400602 0
1982200 156553 0
12904 1845415 0
645314 1677556 1
1363699 1975028 0
1774517 1705053 0
958034 598649 1
1255417...

output:

210379

result:

ok single line: '210379'

Test #38:

score: 0
Accepted
time: 207ms
memory: 20440kb

input:

249996
1670925 231087 0
39527 1983657 0
473410 5370 0
1925481 1720431 0
67352 1896317 0
1504388 1726733 1
267185 1289444 1
1817474 1175113 1
1995074 1664245 0
499013 1967847 0
1648928 1862986 0
1939804 1720616 0
433527 39214 0
1515418 1862505 0
1616861 500050 1
1697588 1794243 0
1208156 242958 1
175...

output:

164113

result:

ok single line: '164113'

Test #39:

score: 0
Accepted
time: 149ms
memory: 14144kb

input:

249952
250574 1778462 0
1826747 837308 1
522919 1819222 0
134196 798730 1
408911 1769945 0
282572 1963935 0
1573844 350523 1
997645 179579 1
545660 1737010 1
1701480 1441783 1
1161949 1833221 1
1551370 59494 0
1532094 214104 0
720104 1906634 0
1336979 258825 1
639637 1880604 0
1678518 3671 0
519444 ...

output:

128606

result:

ok single line: '128606'

Test #40:

score: 0
Accepted
time: 262ms
memory: 21212kb

input:

249962
1570928 1168014 0
1289527 1069368 0
1084465 298630 0
1823246 970084 0
1448051 568213 0
57429 1877382 0
1985663 589872 0
192591 1581816 0
635580 1618658 0
1965199 1744436 0
973848 587670 0
1832568 1364683 0
204794 1526274 0
853401 597947 0
1706385 1388135 0
1394442 748004 0
1927023 1659075 0
1...

output:

23708

result:

ok single line: '23708'

Test #41:

score: 0
Accepted
time: 250ms
memory: 20912kb

input:

249972
884131 132698 0
1506894 1562766 0
777005 1622992 0
1966190 177651 0
367381 942169 0
1988383 6143 0
463050 689081 0
1910856 1788980 0
1840351 978821 0
1209453 1761364 0
434967 1586987 0
1112918 778466 0
1973192 456641 0
1503248 796976 0
1069319 1159757 1
7181 902472 0
923876 1689308 0
1450177 ...

output:

59018

result:

ok single line: '59018'

Test #42:

score: 0
Accepted
time: 110ms
memory: 13508kb

input:

249980
815485 1472579 0
408992 119891 1
613227 536688 0
56071 1821567 1
1798757 1911045 0
477565 1074082 1
934601 373894 0
1789967 302191 0
204776 1469559 1
466130 801703 1
1528053 265224 0
386174 1941600 1
1470080 1248956 0
849523 1043944 0
21679 337669 0
1006660 1824440 0
63376 187202 0
1397095 44...

output:

157728

result:

ok single line: '157728'