QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547621#4371. Spin DoctorPhantomThresholdAC ✓396ms52712kbC++176.5kb2024-09-05 00:18:492024-09-05 00:18:49

Judging History

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

  • [2024-09-05 00:18:49]
  • 评测
  • 测评结果:AC
  • 用时:396ms
  • 内存:52712kb
  • [2024-09-05 00:18:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
typedef long long db;
typedef long long ll;
const db eps=0;
const db INF=1e10;
int sign(db k){
	if (k>eps) return 1;
	else if (k<-eps) return -1;
	return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
 
struct point{
	db x,y;
	point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
	point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
	point operator * (db k1) const{return (point){x*k1,y*k1};}
	db abs2(){
		return x*x+y*y;	
	}
	db dis2(point k1){
		return ((*this)-k1).abs2();
	}
	bool operator < (const point &k1) const{
		int fl=cmp(x,k1.x);
		if (fl==-1) return true;
		if (fl==1) return false;
		return cmp(y,k1.y)==-1;	
	}
	bool operator == (const point &k1) const{
		return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;	
	}
	bool operator > (const point &k1) const{
		int fl=cmp(x,k1.x);
		if (fl==1) return true;
		if (fl==-1) return false;
		return cmp(y,k1.y)==1;	
	}
	int getP(){
		return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);
	}
	friend ostream& operator << (ostream &os,const point &k){
        os << "(" << k.x << "," << k.y << ")";
        return os;
    }
};
 
int inmid(point k1,point k2,point k3){
	return inmid(k1.x,k2.x,k3.x) && inmid(k1.y,k2.y,k3.y);	
}
db cross(point k1,point k2){
	return k1.x*k2.y-k1.y*k2.x;
}
db dot(point k1,point k2){
	return k1.x*k2.x+k1.y*k2.y;	
}

vector<point> ConvexHull(vector<point> A,int flag=1){
	int n=A.size();
	vector<point>ans(n*2);
	sort(A.begin(),A.end());
	int now=-1;
	for (int i=0;i<(int)A.size();i++){
		while (now>0 && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
		ans[++now]=A[i];
	}
	int pre=now;
	for (int i=n-2;i>=0;i--){
		while (now>pre && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
		ans[++now]=A[i];
	}
	ans.resize(now);
	return ans;
}
 
struct Convex{
	int n;
	vector<point> a,upper,lower;
	Convex(vector<point> _a):a(_a){
		n=a.size();
		int ptr=0;
		for (int i=1;i<n;i++) if (a[ptr]<a[i]) ptr=i;
		for (int i=0;i<=ptr;i++) lower.push_back(a[i]);
		for (int i=ptr;i<n;i++) upper.push_back(a[i]);
		upper.push_back(a[0]);
	}
	int sign(long long x){
		return x<0?-1:x>0;	
	}
	void update_tangent(const point &p,int id,int &i0,int &i1){
		if (cross(a[i0]-p,a[id]-p)>0) i0=id;
		if (cross(a[i1]-p,a[id]-p)<0) i1=id;	
	}
	void binary_search(int l,int r,point p,int &i0,int &i1){
		if (l==r) return;
		update_tangent(p,l%n,i0,i1);
		int sl=sign(cross(a[l%n]-p,a[(l+1)%n]-p));
		for (;l+1<r;){
			int mid=(l+r)/2;
			int smid=sign(cross(a[mid%n]-p,a[(mid+1)%n]-p));
			if (smid==sl) l=mid;
			else r=mid;
		}
		update_tangent(p,r%n,i0,i1);
	}
	bool contain(point p){
		if (p.x<lower[0].x || p.x>lower.back().x) return false;
		int id=lower_bound(lower.begin(),lower.end(),(point){p.x,-INF})-lower.begin();
		if (lower[id].x==p.x){
			if (lower[id].y>p.y) return false;	
		}
		else if (cross(lower[id-1]-p,lower[id]-p)<0)
			return false;
		id=lower_bound(upper.begin(),upper.end(),(point){p.x,INF},greater<point>())-upper.begin();
		if (upper[id].x==p.x){
			if (upper[id].y<p.y) return false;	
		}
		else if (cross(upper[id-1]-p,upper[id]-p)<0) return false;
		return true;
	}
	bool get_tangent(point p,int &i0,int &i1){
		if (contain(p)) return false;
		i0=i1=0;
		int id=lower_bound(lower.begin(),lower.end(),p)-lower.begin();
		binary_search(0,id,p,i0,i1);
		binary_search(id,(int)lower.size(),p,i0,i1);
		id=lower_bound(upper.begin(),upper.end(),p,greater<point>())-upper.begin();
		binary_search((int)lower.size()-1,(int)lower.size()-1+id,p,i0,i1);
		binary_search((int)lower.size()-1+id,(int)lower.size()-1+(int)upper.size(),p,i0,i1);
		return true;
	}
};

int main(){
	int n;
	cin >> n;
	vector<point> wp;
	vector<point> bp;
	db cntw=0,cntb=0;
	for (int i=1;i<=n;i++){
		db x,y;
		int col;
		cin >> x >> y >> col;
		if (col==0){
			cntw++;
			wp.emplace_back((point){x,y});	
		}
		else{
			cntb++;
			bp.emplace_back((point){x,y});
		}
	}
	
	if (cntb==1){
		cout << 1 << "\n";
		return 0;
	}
	
	db ans=cntb;
	sort(bp.begin(),bp.end());
	bp.resize(unique(bp.begin(),bp.end())-bp.begin());
	
	vector<point> CHB=bp;
	if (bp.size()>=3) CHB=ConvexHull(bp);
	
//	cerr << "---------------------" << endl;
//	cerr << "Convex Hull of black : " << endl;
//	for (auto e:CHB) cerr << e << endl;
//	cerr << "---------------------" << endl;
	
	if (CHB.size()<=2){
		point st=CHB.front();
		point ed=CHB.back();
		for (auto P:wp) if (inmid(st,ed,P) && sign(cross(P-st,ed-st))==0) ans++;
		cout << ans << "\n";
		return 0;	
	}
	
	ll base=0;
	Convex conv(CHB);
	vector<point> dir;
	vector<pair<point,ll>> vup;
	for (auto P:wp){
		int st=0,ed=0;
		bool flag=conv.get_tangent(P,st,ed);
		if (!flag){
			ans++;
			continue;
		}
		point dirst=CHB[st]-P;
		point dired=CHB[ed]-P;
		if (sign(cross(dirst,dired))<0) swap(dirst,dired);
		
		if (dirst.getP()) dirst=dirst*(-1);
		if (dired.getP()) dired=dired*(-1);
		dir.emplace_back(dirst);
		dir.emplace_back(dired);
		vup.emplace_back(dirst,1LL);
		vup.emplace_back(dired,-1LL);
		if (sign(cross(dirst,dired))<0) base++;
	}
	dir.emplace_back((point){1,0});
	sort(dir.begin(),dir.end(),
		[&](const point &X,const point &Y){
            return sign(cross(X,Y))>0;
        }
	);
	dir.resize(
		unique(dir.begin(),dir.end(),
			[&](const point &X,const point &Y){
        		return sign(cross(X,Y))==0;
        	}
		)
		-dir.begin()
	);
	dir.emplace_back((point){-1,0});
	{
		vector<point> tmp;
		int sz=dir.size();
		for (int i=0;i<=sz-2;i++){
			tmp.emplace_back(dir[i]);
			tmp.emplace_back(dir[i]+dir[i+1]);	
		}
		swap(dir,tmp);
	}
	
//	cerr << "ans : " << ans << endl;
//	for (auto d:dir){
//		cerr << "dir : " << d << endl;	
//	}
	
	auto cmp = [&](const pair<point,ll> &X,const pair<point,ll> &Y){
        int flag=sign(cross(X.first,Y.first));
        if (flag!=0) return flag==1;
        return X.second>Y.second;
    };
	sort(vup.begin(),vup.end(),cmp);
	vector<ll> sumup(vup.size()+1);
    if (vup.size()) sumup[0]=vup[0].second;
	for (int i=1;i<(int)vup.size();i++) sumup[i]=sumup[i-1]+vup[i].second;
	
//	for (auto [vec,val]:dir){
//		cerr << "vec,val : " << vec << " " << val << endl;	
//	}
	
	ll mn=base;
	for (auto d:dir){
		int pos=upper_bound(vup.begin(),vup.end(),make_pair(d,0LL),cmp)-vup.begin()-1;
		if (pos>=0) mn=min(mn,base+sumup[pos]);
	}
	ans+=mn;
	cout << ans << "\n";
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3612kb

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: 3616kb

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: 3572kb

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: 1ms
memory: 3824kb

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: 1ms
memory: 3680kb

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: 78ms
memory: 16956kb

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: 93ms
memory: 15880kb

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: 88ms
memory: 17196kb

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: 105ms
memory: 18484kb

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: 100ms
memory: 16600kb

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: 3856kb

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: 3500kb

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: 3628kb

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: 3844kb

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: 3648kb

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #17:

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

input:

2
0 0 1
0 0 0

output:

1

result:

ok single line: '1'

Test #18:

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

input:

2
0 0 1
0 1 0

output:

1

result:

ok single line: '1'

Test #19:

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

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: 129ms
memory: 9992kb

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: 221ms
memory: 32352kb

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: 129ms
memory: 24780kb

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: 135ms
memory: 24220kb

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: 396ms
memory: 52712kb

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: 39ms
memory: 5412kb

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: 81ms
memory: 17468kb

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: 78ms
memory: 17320kb

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: 84ms
memory: 17300kb

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: 42ms
memory: 5260kb

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: 80ms
memory: 17048kb

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: 211ms
memory: 17756kb

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: 167ms
memory: 11800kb

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: 185ms
memory: 13628kb

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: 362ms
memory: 50060kb

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: 382ms
memory: 51880kb

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: 147ms
memory: 18664kb

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: 181ms
memory: 30996kb

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: 277ms
memory: 52652kb

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: 241ms
memory: 34820kb

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: 321ms
memory: 52332kb

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: 329ms
memory: 52592kb

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: 199ms
memory: 29852kb

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'