QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#93993#4409. 袜子chenshi55 10952ms68876kbC++3.2kb2023-04-04 16:37:592023-04-04 16:38:02

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 16:38:02]
  • 评测
  • 测评结果:55
  • 用时:10952ms
  • 内存:68876kb
  • [2023-04-04 16:37:59]
  • 提交

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[id[i]]=tot[col[id[i]]]++,modify(i,e[id[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) swap(x,y);
			if(!typ){
				for(int k=x;k<=y;++k) modify(k,-e[id[k]]);
				for(int k=x;k<y;++k) for(int $=k+1;$<=y;++$) if(col[id[k]]==col[id[$]]) --e[id[$]];
			}
			A=a[p[i]];B=b[p[i]];sort(id.begin()+x,id.begin()+y+1,Cmp);
			for(int k=x;k<=y;++k) idinv[id[k]]=k;
			if(!typ){
				for(int k=x;k<y;++k) for(int $=k+1;$<=y;++$) if(col[id[k]]==col[id[$]]) ++e[id[$]];
				for(int k=x;k<=y;++k) modify(k,e[id[k]]);
			}
		}
		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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 163ms
memory: 44408kb

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: 159ms
memory: 46292kb

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: 152ms
memory: 45436kb

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: 158ms
memory: 48248kb

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: 164ms
memory: 46980kb

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: 156ms
memory: 45604kb

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: 146ms
memory: 46844kb

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: 151ms
memory: 48736kb

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: 160ms
memory: 48324kb

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: 168ms
memory: 48088kb

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: 9843ms
memory: 60880kb

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: 10046ms
memory: 65756kb

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: 15
Accepted

Dependency #2:

100%
Accepted

Test #13:

score: 15
Accepted
time: 10765ms
memory: 67328kb

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:

ok 500000 numbers

Test #14:

score: 0
Accepted
time: 10952ms
memory: 66652kb

input:

50000 500000
877025 350139 5
-143832 444608 43
455083 449721 13
21366 -923804 47
540152 789728 71
266227 355382 63
-536428 -711034 23
-998154 57875 8
-334074 740620 32
246276 374916 3
-704297 -393685 33
-614894 880828 73
117185 415990 1
-543312 215046 31
215904 -404000 30
-427829 90281 1
427722 -832...

output:

12473373
12408257
12507154
12376650
12213364
12336818
12461889
12194343
12487088
12461889
12287636
12476420
12138920
12375917
12204989
12291029
12374246
12190029
12205841
12475690
12469649
12294925
12269579
12287636
12482573
12465762
12289822
12297787
12462205
12205841
12328257
12465379
12304117
122...

result:

ok 500000 numbers

Test #15:

score: 0
Accepted
time: 10553ms
memory: 66100kb

input:

50000 500000
875409176 -146884605 3
-852555067 779442669 2
-135310615 -25991150 1
-415857031 995015289 37
-761492260 48848870 18
-207602077 -813247088 1
162687832 10213336 1
271929112 682994180 2
-76574267 131873021 1
-368335679 549046786 1
352160629 -463359855 2
782068089 825319998 3
-44672214 4112...

output:

76232923
76121667
75960552
76119621
75585987
75598132
75867079
75861652
75979823
75793380
75639606
75763031
76442133
76022093
76141936
76272184
76131346
75871360
76193620
76011967
75613338
75766062
75994345
75790820
76032783
75617428
75694697
75905128
76046280
75625683
75700183
76007971
76041513
760...

result:

ok 500000 numbers

Test #16:

score: 0
Accepted
time: 10098ms
memory: 66012kb

input:

50000 500000
-598585200 546145949 4
10693995 -846396922 14
789052862 -37923989 1
-492717756 388481199 3
-813901947 -942867382 1
-205123361 865058110 10
221165729 -989130173 7
843701647 164674253 6
-454532857 559818222 3
257996198 793738572 1
775938225 -262839196 1
834834185 -519682962 5
94950096 -12...

output:

149944516
152615583
152192654
149944516
149315628
150312655
152169394
148653173
150202721
151318447
150149019
152077654
150002507
150022335
151425709
152151682
150174510
151274436
150151257
152150221
148682034
149995028
149839542
148012905
153950049
150174510
146646463
150553151
149944516
151744655
...

result:

ok 500000 numbers

Test #17:

score: 0
Accepted
time: 10359ms
memory: 66288kb

input:

50000 500000
378393334 246666269 3
-288429751 -689240591 1
538246474 -179149420 4
19866140 -274604312 1
319383040 694674452 2
9044676 284630066 1
-577379922 -799429128 1
753882987 742757782 1
-748336557 -508913081 1
-744458940 -766779721 1
629312624 888874873 1
345082535 -233888060 9
-198240179 6127...

output:

355919371
357027423
356882073
348068675
341563980
341711918
341993252
351216013
341820581
341247927
355801139
357012424
360549504
345514553
346612456
355801139
345629345
348188018
331432712
334365769
345187709
355645668
353004772
345187709
330517432
341711918
355838156
337808150
331333696
347288304
...

result:

ok 500000 numbers

Test #18:

score: 0
Accepted
time: 10844ms
memory: 65872kb

input:

50000 500000
510087025 -128717769 4
701695438 891659838 17
14091267 -407206760 13
-897701961 -347902519 32
-208038559 -712604275 54
352114405 -467350403 25
665063400 239362902 78
108580609 -287322505 20
979576161 450624747 6
-351660808 883871753 30
626923938 -181807026 32
224172685 -215957127 18
-12...

output:

12457570
12211756
12089072
12451033
12298688
12439757
12320487
12457570
12457570
12317459
12215044
12190106
12226306
12213127
12302925
12067172
12241961
12233658
12442012
12162881
12239648
12467217
12244792
12194336
12312968
12304959
12388042
12468644
12457570
12287858
12241961
12473476
12223586
120...

result:

ok 500000 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

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:


result:


Subtask #5:

score: 15
Accepted

Test #25:

score: 15
Accepted
time: 9517ms
memory: 67888kb

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:

ok 500000 numbers

Test #26:

score: 0
Accepted
time: 9810ms
memory: 68876kb

input:

50000 500000
-798827 -248238 55
-202385 195966 51
-935972 695372 12
-207494 597523 36
828639 839545 1
604085 -878258 28
854907 987889 33
-488652 555674 10
-308758 201373 2
786438 -72867 11
-533482 -614535 58
-853349 714523 60
729730 441018 27
193712 759574 30
-439466 -262414 1
-995124 383459 76
5638...

output:

12116545
1627120
12028488
8327000
11890527
12038075
12100532
30829152
23884384
48253618
0
0
48253618
12079058
4707441
34295749
1085217
12123770
48253618
20695368
11904819
3608287
12253559
0
12074236
12265677
12236373
48253618
12250929
0
11885547
11885547
7336386
12109428
48253618
0
0
36922388
511026...

result:

ok 500000 numbers

Test #27:

score: 0
Accepted
time: 9169ms
memory: 65820kb

input:

50000 500000
916228474 736861331 8
41223569 567024226 2
33633521 -640602439 11
43060388 157896754 9
522582493 -456464181 2
184581697 729182371 8
-915463955 774500464 2
595541741 4861507 3
375567184 -686285601 3
-59758078 -72014188 11
-535452680 -972290610 4
-425062848 998970443 3
776900364 383068694...

output:

73688076
34624304
35713642
74151261
74568055
73687317
80280672
73694989
74197031
74197031
190116467
73477393
74568055
23847839
86652478
126942497
108464771
74197031
125422244
56618750
74568055
73657436
9934358
85804146
74568055
221183265
178732347
73330257
73172655
74197031
73622903
74619669
7449609...

result:

ok 500000 numbers

Test #28:

score: 0
Accepted
time: 9307ms
memory: 66596kb

input:

50000 500000
-218467527 996547968 2
667898126 353067063 1
-703792310 -88011029 3
796101380 -150592337 1
233483304 202627437 1
227009907 -277641383 1
398753734 123601516 1
-932943038 -991506612 1
-586877275 884068330 1
-14924328 992992981 15
-558045242 470672933 7
-305045173 -532112183 7
183202586 80...

output:

34171044
145124721
133863158
322891322
149231859
144059207
201503200
147989909
145302374
145382184
145302231
144074835
144074694
186273717
391942339
147909184
145382184
147909184
45485862
30564622
147909184
13602211
29269333
136955300
161713859
145417496
411765627
144050978
147901245
147744158
30332...

result:

ok 500000 numbers

Test #29:

score: 0
Accepted
time: 9156ms
memory: 66016kb

input:

50000 500000
-209258179 -13673102 2
-536850965 -914833237 1
-859835086 -387099479 7
650316207 -949976551 2
490090099 432733293 1
295590818 336348152 1
-924146823 -481896977 1
-688990212 -402275949 1
905552333 225834084 1
100755207 -115968339 5
409919132 761133402 1
-486717813 -425455505 1
-448210451...

output:

342217921
351225756
335443425
351262509
109504291
342519167
344283077
344283077
335848738
803468818
538859665
335443425
344283077
344548834
351534475
335399668
765872733
216202376
344283077
335363755
351409541
51890336
201074052
335443425
351534475
335363755
351452899
124534601
342217921
351828683
3...

result:

ok 500000 numbers

Test #30:

score: 0
Accepted
time: 9593ms
memory: 66264kb

input:

50000 500000
-683034611 -711257501 27
60004722 -761142590 25
661166166 -468685357 7
849005124 -979617930 65
-844130034 690778896 26
420045533 -127259351 21
770352203 284425974 4
767529443 -311119877 25
-773073204 -708678356 61
-616770488 -127741421 27
-439194801 -804840917 7
-102517861 -591985498 15...

output:

5176455
36752777
12349440
9037077
11988285
12249163
12230497
6719556
12344687
12249163
11988285
12055113
31826512
12074401
15191922
32592923
12074401
12358058
10249606
12249163
11988285
12009512
12074401
12067085
11988285
12074401
12345034
12349440
12074401
11998182
12074401
23409470
1079840
2820121...

result:

ok 500000 numbers

Subtask #6:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #31:

score: 10
Accepted
time: 3355ms
memory: 66148kb

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: 3417ms
memory: 66724kb

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: 3208ms
memory: 65272kb

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: 3295ms
memory: 63644kb

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: 3208ms
memory: 64932kb

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: 3362ms
memory: 65184kb

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:

100%
Accepted

Dependency #4:

0%