QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93979#4409. 袜子chenshi25 10189ms65756kbC++3.2kb2023-04-04 12:58:022023-04-04 12:58:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-04 12:58:07]
  • 评测
  • 测评结果:25
  • 用时:10189ms
  • 内存:65756kb
  • [2023-04-04 12:58:02]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=5e5+10,B=800;
int n,m,X[o],Y[o],col[o],a[o],b[o],c[o],p[o],idinv[o],cnt[o],tot[o],e[o];long long d[o],ans[o];vector<int> vec[o];
struct Query{int a,b,c;};
struct Slope{
	int x,y;
	Slope(int x_,int y_):x(x_),y(y_){}
	inline int Quadrant()const{
		if((x==0&&y<0)||(x>0&&y<0)) return 0;
		if((x>0&&y==0)||(x>0&&y>0)) return 1;
		if((x==0&&y>0)||(x<0&&y>0)) return 2;
		return 3;
	}
	inline bool operator<(const Slope&b)const{
		if(Quadrant()^b.Quadrant()) return Quadrant()<b.Quadrant();
		return x*1ll*b.y-y*1ll*b.x>0;
	}
};
namespace foobar{
int n,A,B;bool typ;vector<int> id;vector<pair<Slope,pair<int,int> > > s;
inline int lowbit(int x){return x&-x;}
inline void modify(int pos,int val){for(++pos;pos<=n;pos+=lowbit(pos)) d[pos]+=val;}
inline long long query(int pos){long long res=0;for(++pos;pos;pos-=lowbit(pos)) res+=d[pos];return res;}
inline bool Cmp(int i,int j){return A*1ll*X[i]+B*1ll*Y[i]<A*1ll*X[j]+B*1ll*Y[j];}
inline void slv(){
	if(id.empty()) return;
	n=id.size();vector<pair<Slope,pair<int,int> > >().swap(s);
	A=0;B=-1;sort(id.begin(),id.end(),Cmp);
	for(int i=0;i<n;++i) for(int j=i+1,x,y;j<n;++j){
		x=X[id[j]]-X[id[i]],y=Y[id[j]]-Y[id[i]];
		Slope t1(y,-x),t2(-y,x);
		if(t2<t1) swap(t1,t2);
		s.push_back(make_pair(t1,make_pair(id[i],id[j])));s.push_back(make_pair(t2,make_pair(id[j],id[i])));
	}
	sort(s.begin(),s.end());
	for(int i=0;i<n;++i) idinv[id[i]]=i,d[i+1]=0;
	if(!typ) for(int i=0;i<n;++i) e[i]=tot[col[id[i]]]++,modify(i,e[i]);
	for(int i=1,j=0,sz=s.size(),l,r,md;i<=m;++i){
		for(int x,y;j<sz&&s[j].first<Slope(a[p[i]],b[p[i]]);++j){
			x=idinv[s[j].second.first];y=idinv[s[j].second.second];
			if(x>y) continue;
			if(!typ){
				modify(x,-e[x]);modify(y,-e[y]);
				for(int k=x+1;k<y;++k){
					if(col[id[x]]==col[id[k]]) --e[k],modify(k,-1),++e[x];
					if(col[id[y]]==col[id[k]]) ++e[k],modify(k,1),--e[y];
				}
				if(col[id[x]]==col[id[y]]) ++e[x],--e[y];
				swap(e[x],e[y]);
				modify(x,e[x]);modify(y,e[y]);
			}
			swap(id[x],id[y]);swap(idinv[id[x]],idinv[id[y]]);
		}
		for(l=-1,r=n-1;l<r;){
			md=(l+r+1)/2;
			if(a[p[i]]*1ll*X[id[md]]+b[p[i]]*1ll*Y[id[md]]+c[p[i]]<0) l=md;
			else r=md-1;
		}
		if(typ) cnt[p[i]]+=l+1;
		else ans[p[i]]+=query(l)*2+l+1;
	}
	vector<int>().swap(id);typ=0;
}
}
inline bool cmp(int A,int B){return Slope(a[A],b[A])<Slope(a[B],b[B]);}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d%d",&X[i],&Y[i],&col[i]),vec[col[i]].push_back(i);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]),p[i]=i;
	sort(p+1,p+m+1,cmp);
	for(int i=1;i<=n;++i) if((int)vec[i].size()>=B){
		for(int j=1;j<=m;++j) cnt[j]=0;
		for(int j=0,sz=vec[i].size();j<sz;++j){
			if(j%B==0) foobar::slv(),foobar::typ=1;
			foobar::id.push_back(vec[i][j]);
		}
		foobar::slv();
		for(int j=1;j<=m;++j) ans[j]+=cnt[j]*1ll*cnt[j];
	}
	for(int i=1;i<=n;++i) if(!vec[i].empty()&&(int)vec[i].size()<B){
		if((foobar::id.size()+vec[i].size())>B) foobar::slv();
		for(int j=0,sz=vec[i].size();j<sz;++j) foobar::id.push_back(vec[i][j]);
	}
	foobar::slv();
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 147ms
memory: 45684kb

input:

1000 1000
8756 4483 237
-7891 -2818 114
8667 -7202 36
8150 -2 248
-4483 -9934 375
-9669 -1815 802
4008 9788 22
-2193 -4988 307
-9813 -4926 22
6344 8542 93
-9906 -9906 38
-3791 -2822 814
-7118 8408 51
-779 9589 3
-3211 1342 73
2346 -6502 112
31 -5037 6
3714 -4554 118
8788 6735 533
3860 -4232 5
3257 6...

output:

1047
1034
1001
1061
1060
956
1029
1001
1048
1001
1052
1023
1077
0
1077
1015
1060
1012
1022
1022
1077
1369
993
1001
1060
1003
1077
1034
1063
0
1001
1038
0
1001
1077
1001
1063
1063
1060
1034
0
1060
1060
1077
1031
1021
939
1023
849
1001
1060
1000
1008
1150
1007
878
1060
1060
1020
1043
1045
1077
1048
0
...

result:

ok 1000 numbers

Test #2:

score: 0
Accepted
time: 141ms
memory: 46784kb

input:

1000 1000
-809378 594895 7
-463965 286585 108
492337 -110361 235
163858 -391125 15
-546105 -878318 214
360416 -730538 407
-298417 -177165 227
752631 -788118 51
17699 323971 105
843170 208717 105
766811 396573 69
127415 309072 39
637608 -188063 352
224425 -952868 139
850507 751278 110
-995626 648647 ...

output:

997
969
935
993
9
1023
998
1014
999
969
1001
982
1023
937
1028
1035
973
1029
953
969
25
1001
889
976
985
1023
937
1023
1006
992
937
1009
1023
969
969
1001
925
937
969
1001
969
1023
937
937
1000
1023
969
932
962
1001
969
994
937
1001
937
905
1008
937
1023
958
1023
1001
731
1015
956
988
945
970
1042
9...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 133ms
memory: 45432kb

input:

1000 1000
-329387625 -341019218 102
13965986 806087844 9
-528171131 227425809 15
786487633 15830440 3
539535861 -963497336 7
-742845817 -372626578 35
-787231340 -132749801 3
-543467667 -942295910 119
-672244153 -833463748 15
-641088972 317851104 1
65665573 -823079703 26
247807062 -882007619 11
-6610...

output:

4529
5025
4868
4426
3446
3771
3781
3700
4842
4604
4259
3557
3731
3538
3979
4367
4879
3595
4336
3446
4754
3632
3762
3750
3446
4879
4728
4668
4610
3781
4816
3600
3760
4868
3760
3446
4387
3446
3760
4529
4447
4019
4879
3781
3611
4529
4529
4865
4711
3446
4868
4104
3446
3760
3781
3387
4647
4736
4519
3730
...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 167ms
memory: 44768kb

input:

1000 1000
-240930145 126765047 4
5029224 -538225798 8
748056353 -6881636 1
254300626 659262809 8
590237623 -34857701 1
655683714 -171537454 3
582680000 -835569740 4
-746501072 381914331 1
-696675178 165921148 6
73362513 -665223969 4
-204185218 875019442 5
-656420293 -589534031 5
-326306612 -57437624...

output:

23040
20550
23040
23667
19699
22762
21160
20433
22290
21231
20550
21874
20500
20550
23040
22949
23485
24394
21591
24045
19681
20491
21324
22226
20082
24060
20505
23603
19699
20550
21488
23667
20491
19699
23667
21061
21600
20550
21015
21876
22917
22481
23040
22902
19699
20858
19699
21919
21725
20490
...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 145ms
memory: 45472kb

input:

1000 1000
-886939246 -956433905 4
458364194 -989591596 1
-69057070 -647489199 2
-34535206 -500686466 1
671489436 -224022957 1
-487072455 294047705 4
-284801195 490213612 1
27112031 -736294945 1
-408100248 967227200 4
107685527 147821041 1
-759670783 -778138619 7
554606387 -117974098 2
-543318085 -66...

output:

126533
125819
126518
116416
115569
112523
113786
120221
115569
126703
126174
125954
113560
113560
115569
129937
124149
120150
115569
120801
119337
129285
126174
126174
127311
119240
120252
127733
124149
113560
113560
115569
115936
130657
120313
120798
115569
131931
112735
120197
123145
115569
120234...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 138ms
memory: 44656kb

input:

1000 1000
-140707073 -709357437 276
666979616 294563099 34
507506113 -978340110 245
-41619729 -632363033 28
450190358 -768866476 86
-106476442 -83684337 574
477466216 479545563 220
196637637 -181541675 119
427079800 435777395 406
30465211 86113444 760
129968522 814179371 129
719311691 325225596 48
-...

output:

1003
986
1063
1104
1058
1054
1004
1018
1011
1082
1065
1009
967
1081
1071
964
1014
964
1015
1030
1010
1059
1019
1027
1062
1027
1006
1064
1081
1027
1086
1037
1015
995
1081
1000
1015
1056
1014
1005
966
1024
1095
1003
1012
993
1081
1003
1058
1027
1039
1015
1045
1014
967
1003
1014
959
1047
1006
1014
1082...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 138ms
memory: 44572kb

input:

1000 1000
-447447700 -591263241 63
-216023636 -506993336 886
-723265777 481650149 2
380816011 -971341762 11
-433458798 217059466 113
-649457481 318097209 59
998475552 -512422664 128
-293129715 -964655164 511
-403596696 -668671938 515
-212213731 -448158397 80
-761541201 -739537496 122
-686289475 -803...

output:

914
914
940
960
991
1045
1051
1053
1029
1015
914
1092
961
1051
958
988
1032
1051
1092
961
961
946
1051
1037
961
986
1023
1009
1051
1057
1044
1092
1025
1092
956
914
980
1087
927
1092
1005
1006
969
999
1002
914
914
1041
932
1031
1056
1048
1058
1070
1027
1092
1057
964
1051
961
1051
1064
1062
914
971
10...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 132ms
memory: 48600kb

input:

1000 1000
-541722175 476510525 31
628338000 759271580 381
-271238678 800070438 512
780664157 -680638999 186
-426546737 121982760 93
270959547 -103484346 577
-598325723 -197010965 114
112923702 786079875 121
-519492810 -842104927 16
555941748 784488471 103
-689093484 169597790 85
-164649986 -99979169...

output:

1004
885
1009
950
994
1095
1008
1071
1016
862
958
1009
1095
1054
1007
1007
1095
1007
1082
1095
1095
885
890
1009
913
1042
987
885
885
1071
886
1065
1009
1007
1005
1121
888
1033
918
1074
1051
1042
885
1008
1004
1009
1095
1095
1007
1102
1052
1028
1089
1095
905
890
1027
1095
1095
1129
1007
885
1029
103...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 142ms
memory: 46448kb

input:

1000 1000
223130280 -358540334 70
-446423718 -649264507 25
952545239 -115890499 74
198701646 411091447 52
-543555719 -183987016 671
-138533088 462438454 72
780376261 275581957 624
-269723997 -448427286 73
706578440 987790609 157
-804222735 801819299 503
915059774 569425246 54
-221158650 -190676516 2...

output:

1022
1010
1032
1085
978
1022
927
948
1032
1081
1030
948
1018
980
965
936
1022
1010
1010
1016
942
1030
1030
948
1022
950
1010
1022
1032
948
937
960
1011
1010
1010
1022
1067
1010
1095
1017
980
1070
948
1019
964
1045
1022
1069
1029
1086
1022
1010
948
1010
984
944
1010
1010
949
1030
985
957
943
1028
107...

result:

ok 1000 numbers

Test #10:

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

input:

1000 1000
-580044540 7764137 285
-849966519 -358165808 235
877921194 265967662 564
304785558 62822807 48
116178894 720156161 210
894895305 -213358952 51
655074511 -309026876 195
296310508 -237014578 134
-255019899 626409905 55
-557361321 990535673 287
106143372 -769370053 523
-935285432 -394592511 8...

output:

887
862
1006
824
927
883
1017
1020
1010
909
1022
1006
942
855
1051
912
885
876
873
862
1032
892
883
1032
909
1007
912
862
841
876
1010
1033
912
883
985
862
1006
912
930
912
985
1021
934
1006
808
873
1034
1006
1032
912
862
1030
1000
880
1009
824
1032
894
1092
873
1085
1006
1031
888
937
909
1032
1006
...

result:

ok 1000 numbers

Subtask #2:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 9268ms
memory: 64420kb

input:

50000 500000
384309433 -953786733 1
-381089810 891795502 1
-701194776 440247159 1
-403243027 539105336 1
275206790 -652250203 1
-554746251 903743804 1
-457035253 912757156 1
-342310772 -17612092 1
-440332191 682239316 1
730332275 816145283 1
-701691234 -908289789 1
-632861504 -277378843 1
-567495050...

output:

618496745
614079729
616866497
614478068
613189405
616715138
615126465
616114802
614529490
614077984
616764805
614626805
615475280
615176840
617956645
618705730
613485153
614626805
614626805
612802541
617062849
617662305
613684025
618496745
612900340
615420738
613682609
617857600
616568900
614626805
...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 9375ms
memory: 64696kb

input:

50000 500000
729905 -125985 1
926315 959640 1
123096 -91945 1
-186481 965101 1
-425756 271410 1
-158109 -800982 1
122987 441100 2
-732281 918630 1
182284 -51080 1
-380410 -929492 1
472062 848544 1
671209 376870 1
366165 -263178 1
-539467 -62456 1
942084 68081 1
384749 792849 1
-648204 -741411 2
7878...

output:

398628245
392170825
389391829
388440685
392182688
387805108
381517693
384525010
390830690
397720525
391054036
392346085
516745745
395682701
395754553
388205365
395821634
398565154
1051363802
385964164
387885617
390926962
22605145
389138933
386438306
387558676
390944065
392346085
398628245
391344637
...

result:

ok 500000 numbers

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #13:

score: 0
Wrong Answer
time: 10189ms
memory: 65160kb

input:

50000 500000
-9418 -1818 20
7456 -4051 11
2408 1036 12
9188 -5797 26
-2810 -6058 10
-1870 -5476 15
-4838 3308 10
-7573 -547 12
-8221 -6779 58
4436 -6839 78
-5131 -5558 31
-636 7994 15
3144 8637 2
-9161 -7142 63
-5699 -3454 72
-5585 3911 7
6193 -8685 68
6768 1154 37
-5097 -5253 9
7322 6256 8
-4366 71...

output:

12323846
12427135
12344036
12062617
12466352
11630227
12036161
12050157
12062549
12419726
20506205
12059447
12027445
12313309
12216296
10607828
0
15278549
15242701
48910334
12548226
12076087
12062617
13714531
12245560
12030548
12017793
18674164
12056369
12691062
12435069
12440010
48910334
12163067
1...

result:

wrong answer 591st numbers differ - expected: '14118464', found: '14116539'

Subtask #4:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 9695ms
memory: 65252kb

input:

50000 500000
2598 -1000000 6
1388 -1000000 3
5492 1000000 8
-1000000 -3573 23
-1000000 -7880 15
-4285 1000000 7
1000000 5211 5
-1000000 5915 79
7147 -1000000 29
-9495 -1000000 25
9028 1000000 1
1000000 -4880 20
-8498 1000000 53
1000000 -4256 22
3107 -1000000 29
2061 -1000000 45
8876 -1000000 76
-279...

output:

12162691
12234856
12164084
12162691
12161484
12164084
12162691
12157836
12258260
12231963
12236398
12176350
12164084
12225490
12162691
12237049
12226003
12164084
12237262
12162691
12164084
12234856
12226003
12234856
12162691
12237049
48739336
12214677
12162691
12256061
12162691
12162691
12164084
122...

result:

wrong answer 348th numbers differ - expected: '12173369', found: '12171486'

Subtask #5:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 8899ms
memory: 64768kb

input:

50000 500000
407 -5105 53
6211 98 81
7444 6196 1
-4294 -9353 26
4316 -3143 1
7144 2361 17
6364 -2245 14
-8684 -6564 3
6269 -687 2
-3139 5693 12
-9991 6547 20
2179 2178 47
-6588 7830 21
-6216 -200 3
9207 8834 24
9388 -5953 31
7752 4125 39
7875 -5517 22
-4701 2244 12
8088 3158 4
-4446 3467 1
-1002 154...

output:

10325005
11474809
0
0
11518032
0
0
49015742
49015742
49015742
0
11392831
0
49015742
0
13876057
0
13339251
10553686
49015742
49015742
49015742
14634637
0
0
49015742
49015742
0
11099497
49015742
11282162
0
0
49015742
0
49015742
0
49015742
49015742
49015742
0
49015742
13190125
13266876
0
0
10953869
116...

result:

wrong answer 78045th numbers differ - expected: '36210682', found: '36211053'

Subtask #6:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #31:

score: 10
Accepted
time: 3019ms
memory: 64336kb

input:

20000 200000
6638 9179 76
-6000 442 3
3879 -6574 7
8687 4572 8
3147 5179 38
253 -9723 3
-7740 -1232 4
-3694 -5085 2
404 8299 31
-7760 -1678 9
-1545 2578 10
-1619 -3470 60
8213 5421 30
3532 -3882 33
-7243 -4051 16
8061 7004 47
-1210 -2676 7
466 1969 20
4548 1421 34
-7818 -6690 5
-4934 -9618 1
-2580 -...

output:

1758698
7647866
0
7647866
7647866
7647866
7647866
0
1635548
0
0
1653656
1748652
7647866
0
0
0
1818126
0
1670265
7647866
7647866
7647866
117560
7647866
2211850
7647866
1706734
7647866
3819707
0
7647866
7647866
0
0
2005011
0
2081748
0
0
0
7647866
7647866
0
7647866
0
7647866
0
7647866
7647866
1853071
0...

result:

ok 200000 numbers

Test #32:

score: 0
Accepted
time: 3060ms
memory: 64224kb

input:

20000 200000
78296 871705 2
-321786 -223939 55
206321 13301 5
936459 953224 2
786679 -207659 4
-344982 138785 7
-679393 625365 23
471779 -234292 4
309023 387746 40
552469 -85365 47
-249315 -212920 17
760830 -73928 6
372279 -74882 67
250928 40245 2
113230 893088 24
825605 -900412 16
-97442 20555 38
4...

output:

0
1977860
4936377
7696888
1954788
5786368
215261
1526406
0
1960128
0
1872175
7696888
0
3348197
1900942
457581
135358
0
178251
1957422
190903
0
7696888
1899809
0
1877839
1956585
831741
1980824
7696888
1877230
1983876
1983161
7696888
1894267
1877839
1901712
0
0
7696888
1313985
125818
0
526858
1962369
...

result:

ok 200000 numbers

Test #33:

score: 0
Accepted
time: 2953ms
memory: 65756kb

input:

20000 200000
652486619 -31021686 3
674095691 464638171 4
15422233 759985277 3
562107322 412005266 1
139860761 796741739 8
698712467 -590901499 1
522238215 626704636 1
201348077 -408723082 1
39872091 715972308 1
796098329 -286661044 2
919206004 -469492740 1
-383301172 -29536420 3
53882519 861839374 2...

output:

11771013
31274335
11879033
35912140
11726284
4205341
11733792
11717495
12782396
11771013
11771013
10070328
11869954
23720452
11771013
11879033
22429986
11922585
11722958
11879033
31338181
20862487
11879033
9810882
11879033
11726284
11892271
23710360
11278574
11929578
11771013
11712074
11879033
52664...

result:

ok 200000 numbers

Test #34:

score: 0
Accepted
time: 3093ms
memory: 62088kb

input:

20000 200000
-795353471 115084011 13
-563296752 -456325938 1
-674289346 95689857 1
-92044055 754798599 9
-675839663 21811860 1
506687221 -419286981 2
-884311516 -454927818 2
-755930287 188852928 1
-581091496 -419381474 3
-728317641 229096947 1
338056790 -39273736 19
-210691940 -469787431 1
-38255758...

output:

1912895
23547122
23547122
23844021
24004015
18462397
62340461
24036205
5430123
24004015
23567973
23825729
9884613
23844021
66985157
23466766
21626963
23400133
69769389
23864900
24023548
2171328
23469795
2845135
23400133
23864900
16852015
23844021
67005381
23795237
23616691
9291007
23586309
23937167
...

result:

ok 200000 numbers

Test #35:

score: 0
Accepted
time: 2989ms
memory: 62340kb

input:

20000 200000
597487142 -264327080 1
363097870 -93832409 2
-133170749 -255087340 1
-93165077 880837061 2
-776244068 -942115532 1
-66302342 914936080 1
-543471400 321627441 1
-763297145 903202513 1
964264167 997147840 1
404083309 -28792558 1
7173459 -840908932 1
-133986760 895564657 1
913858985 -98644...

output:

32223218
53872063
55494198
144056178
140092438
32866170
23323015
54143424
53961016
54056940
53872063
22182709
53797992
97450256
55523430
54071349
53872063
88284830
93898674
154834759
4565025
53872063
55215190
82673062
55584499
54071349
53872063
54143424
55494198
124251547
55310638
55584499
10314775
...

result:

ok 200000 numbers

Test #36:

score: 0
Accepted
time: 3000ms
memory: 65172kb

input:

20000 200000
-941638561 360399266 28
933472562 827467156 29
142596199 -312313142 19
-701859452 784478711 53
-167771199 -602390645 67
-232270233 571628419 12
252628776 98913281 37
239060250 520487898 35
80892487 -258989235 28
44250745 868627770 45
132973358 -275683185 14
884510982 108814973 66
903390...

output:

1968291
1970567
1934739
1936879
1968291
1936879
1963847
1956137
3933707
1494847
1936879
945467
5455966
430262
1936879
1963847
1950287
3124096
1954982
642280
1953891
363771
1954805
1958139
1956137
1956000
4377693
1932276
1936879
1968291
1934739
4995468
1952387
1936879
1936879
1952387
1288909
5187460
...

result:

ok 200000 numbers

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%