QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296119#5072. Future CoderzyzakioiWA 581ms18244kbC++141.2kb2024-01-02 10:11:222024-01-02 10:11:23

Judging History

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

  • [2024-01-02 10:11:23]
  • 评测
  • 测评结果:WA
  • 用时:581ms
  • 内存:18244kb
  • [2024-01-02 10:11:22]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
int t, n, a, cnt;
vector<int>pos, neg;
int get1(int now) {
	int l = 0, r = pos.size() - 1, mid, ans = pos.size();
	while (l <= r) {
		mid = (l + r) >> 1;
		if (pos[mid] * now < pos[mid] + now) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return pos.size() - ans;
}
int get2(int s, int e, int now) {
	int l = s, r = e, mid, ans = s;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (pos[mid] * now < pos[mid] + now) {
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	return ans - s;
}
signed main() {
	cin >> t;
	while (t--) {
		cin >> n;
		pos.clear();
		neg.clear();
		for (int i = 1; i <= n; ++i) {
			cin >> a;
			if (a > 0)
				pos.push_back(a);
			else if (a < 0)
				neg.push_back(a);
			else
				++cnt;
		}
		sort(pos.begin(), pos.end());
		sort(neg.begin(), neg.end());
		long long ans = 0;
		for (auto i : neg)
			ans += get1(i);
		for (int i = 0; i < pos.size(); ++i)
			ans += get2(i, pos.size() - 1, pos[i]);
		ans += cnt * pos.size();
		cout << ans << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
8
3 -1 4 1 -5 9 2 -6
1
0

output:

19
0

result:

ok 2 number(s): "19 0"

Test #2:

score: 0
Accepted
time: 581ms
memory: 3620kb

input:

1000000
1
-164353707
1
-282757533
1
916961328
1
-540297420
1
866372576
1
1
1
871062154
1
873753814
1
1
1
1
1
636976909
1
789718633
1
200630859
1
-855838121
1
1
1
1
1
282306491
1
-308064257
1
-220028474
1
396002423
1
765070684
1
407981535
1
1
1
184126913
1
935672434
1
-70908999
1
1
1
669665925
1
1
1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 numbers

Test #3:

score: 0
Accepted
time: 347ms
memory: 3624kb

input:

500000
2
1 790170188
2
-886864567 1
2
-579023597 746881890
2
-534254391 -756978339
2
1 1
2
-617821991 -444756587
2
-676343428 -276446748
2
-422136307 1
2
1 1
2
-280282708 -901772076
2
-958271412 676715004
2
157313986 920829551
2
1 1
2
-796480068 1
2
1 1
2
616588559 1
2
1 -922399591
2
620860427 1
2
-...

output:

1
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
1
0
1
1
1
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 302ms
memory: 3616kb

input:

333333
3
-456843986 158506254 -534204016
3
1 813811307 1
3
1 -670006360 -532705717
3
-254727252 981735583 1
3
-225553465 -935705776 1
3
-988632504 1 1
3
-178872231 -583515677 1
3
623311036 -686255588 1
3
-737001211 1 392980906
3
18055918 1 -646425457
3
1 410678121 356903351
3
-236953261 -340219283 -...

output:

2
3
2
3
2
3
2
3
3
3
2
0
0
3
2
2
2
3
3
2
2
0
3
0
2
3
3
2
3
3
0
0
3
3
3
3
2
2
3
2
2
0
2
0
3
3
2
3
2
2
2
3
2
3
2
2
3
2
3
0
3
2
2
3
2
3
0
3
3
2
3
2
0
2
2
0
2
3
2
3
3
3
0
3
3
3
0
3
2
2
3
0
2
2
2
0
2
3
2
3
3
2
2
2
2
3
3
2
3
3
3
0
2
2
3
2
3
2
2
3
3
2
3
0
3
3
3
3
2
2
3
3
3
2
3
3
3
3
2
3
3
3
3
0
0
3
2
2
3
3
...

result:

ok 333333 numbers

Test #5:

score: 0
Accepted
time: 292ms
memory: 3708kb

input:

200000
5
313866785 1 1 332623105 1
5
334914680 1 194045152 1 1
5
913547424 828356629 1 318514317 463423920
5
-966604134 -394859623 -546920218 1 -475480757
5
911091114 -965977622 -623955994 -821624784 1
5
122007245 1 515943642 -958411032 1
5
-365415275 1 724364010 -425774782 -588760639
5
-976139440 1...

output:

9
9
4
4
7
9
7
9
6
6
4
7
8
7
4
10
9
7
9
7
9
10
8
9
7
9
9
8
9
10
10
7
7
10
9
7
4
4
10
9
6
9
10
9
9
9
9
4
9
9
9
10
8
9
4
9
6
4
9
7
8
7
7
7
7
10
4
9
8
9
9
10
7
9
9
10
7
7
8
10
9
9
10
4
9
7
7
7
9
9
9
7
8
8
9
4
7
7
8
7
9
6
4
7
8
10
9
4
7
7
6
6
7
7
8
8
10
8
7
4
9
9
9
9
6
8
6
8
6
7
7
7
10
9
9
9
7
9
6
7
10
7...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 235ms
memory: 3620kb

input:

100000
10
18068807 665885439 1 1 -2862331 223630963 316366506 -474236418 1 -382176675
10
1 201015992 359736557 473174856 424044050 -323477656 129444459 541668958 1 791240074
10
1 -334263857 1 1 1 -629142457 740241044 1 1 1
10
-69729129 19893939 -454991275 418716614 698053473 177178246 843340692 1 -3...

output:

36
24
44
27
35
27
32
29
39
38
39
41
29
30
36
39
32
36
17
42
41
38
41
33
34
33
38
34
39
29
29
32
32
29
36
35
34
25
27
34
35
32
36
30
36
17
41
36
35
34
24
36
33
35
36
29
39
32
30
23
34
17
29
32
27
24
29
32
34
41
39
30
27
32
33
36
38
23
34
29
43
33
32
38
30
43
38
36
34
39
39
42
36
29
38
29
34
29
29
36
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 232ms
memory: 3688kb

input:

10000
100
742189771 1 104362715 -508913885 -966596725 529680000 303155662 329730769 776744919 602196557 985408061 959317657 -229768261 -981695323 -971828593 31678627 1 809632782 427378586 1 -762586269 -428528786 -24043242 366495643 -455501573 1 -337736679 -352408190 -431766238 303924054 -540026786 1...

output:

3926
3723
3609
3719
3617
3467
3894
4107
3744
3987
3803
3926
3554
3504
3686
3855
3954
3582
3954
3618
3827
3890
3626
3957
4193
3554
3723
3983
3764
3794
3681
3789
3735
3859
4016
3922
3859
3984
3859
4110
3614
3689
3878
3969
3841
3579
4067
4019
3855
3989
3554
3983
4076
3779
4154
3894
3782
4055
4110
4050
...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 243ms
memory: 3624kb

input:

1000
1000
799675571 -147968613 935620048 724246778 487114192 346596834 378670063 27796944 -951842007 -102859312 -373060982 542829748 -351959523 -434320520 -323683332 734883536 152033886 1 -584793481 336220497 217919037 909497937 -855764710 1 1 -659362222 1 795745826 353787300 -494723929 1 206014470 ...

output:

395816
385254
381008
388022
384231
391910
387788
382517
382230
388479
383335
387529
381779
382516
388371
386939
388242
381504
381821
390926
388908
389118
385398
394494
388934
391488
388934
388814
385226
380595
386156
388919
383391
384237
384523
386574
391844
380463
391536
379758
392529
384774
388928...

result:

ok 1000 numbers

Test #9:

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

input:

100
10000
719870830 -352100131 709937014 572622881 604184377 -210915406 1 -913240674 -403693546 717949766 812371661 -321027479 1 528674382 1 -415654942 1 368884126 111017614 331104804 1 1 -442301304 1 -965207861 24312770 801936514 1 900862682 1 1 1 -970462441 -539712661 1 902604312 314530973 1 -1235...

output:

38802434
38776923
38929334
38518261
38522529
38661674
38584709
38834534
38769609
38928129
38899229
38423228
38728406
38589231
38547861
38753594
38558154
38476022
38604193
38601925
38778599
38858729
38783244
38677748
38896989
38480468
38475344
38708231
38889155
38822069
38835835
38696711
38975776
385...

result:

ok 100 numbers

Test #10:

score: 0
Accepted
time: 265ms
memory: 4696kb

input:

10
100000
1 1 1 -826727751 1 1 1 994561710 30875659 451531117 -613181225 -939124713 -302107149 -524962718 599224276 1 -893343886 -476139259 1 -392048340 452792359 365990035 419735825 -281226601 233858845 -508639066 -716578294 1 -329202930 -868474727 1 1 204347154 -993309867 -954688030 1 -614549993 3...

output:

3888463079
3875815289
3887803404
3881233365
3877531899
3877406400
3882421754
3874118223
3868092869
3878564525

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 260ms
memory: 4604kb

input:

10
100000
-122582831 -600037920 101001605 -438694939 -295712621 1 -438659998 -737589851 370687908 1 -545621665 1 1 89841290 -61642105 274057992 -368951270 -21499741 1 -172728940 -429892874 -557496719 299378737 118428150 1 1 1 -401093659 -495653276 599152756 1 896361702 -900598995 511597965 1 7518184...

output:

3877271969
3874158232
3871084584
3873537735
3874129050
3878206810
3883100904
3868290843
3880238778
3878907468

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 276ms
memory: 18244kb

input:

1
1000000
-667373390 280487798 1 1 1 -766422426 399232521 847629585 1 655312241 157670619 687626034 -200625353 -804824338 1 613276861 1 -713419387 1 592106539 -282921968 540840171 -655201339 904916903 1 -727617963 1 -259019351 1 1 -607516081 1 614705495 -475556582 -210171528 1 -913004294 571740512 5...

output:

387775170212

result:

ok 1 number(s): "387775170212"

Test #13:

score: 0
Accepted
time: 273ms
memory: 16608kb

input:

1
1000000
223843475 1 198303459 918528278 648615205 1 1 -83749218 1 248939114 1 43487845 126454153 1 1 -764157201 459633267 844902448 589441232 1 1 1 -16445037 749102015 1 -741440756 -477036417 -878864628 589542835 -906426699 29827995 747968690 223715418 1 1 -876859565 559975222 1 -531710724 5433042...

output:

387919742844

result:

ok 1 number(s): "387919742844"

Test #14:

score: 0
Accepted
time: 267ms
memory: 17016kb

input:

1
1000000
-843504022 263065141 -675598306 1 619134990 1 549452845 708287641 625746540 1 1 1 1 1 1 -755621094 882472549 -726731700 -779321318 983847217 193859527 -407914470 513306972 1 1 1 -628382567 128579146 1 160037431 1 1 -384797017 790056771 51775292 -178064558 355255537 369525548 1 1 889398342 ...

output:

387972032558

result:

ok 1 number(s): "387972032558"

Test #15:

score: 0
Accepted
time: 271ms
memory: 17212kb

input:

1
1000000
1 1 1 1 -571577427 1 372835328 1 1 -459244424 360949619 488949341 -269440189 1 516177878 209450912 272730077 -820248412 -127974173 1 -867322552 -494527428 948494225 -658931435 361690180 526189481 1 137230040 -732361379 564744545 696106595 -422353886 1 902804134 -820955936 -337168447 1 1 76...

output:

387689271521

result:

ok 1 number(s): "387689271521"

Test #16:

score: 0
Accepted
time: 274ms
memory: 17588kb

input:

1
1000000
555575182 -489550674 -57491130 1 48387813 1 144123688 -396444255 928098385 -47742952 930268309 -999273581 -42854339 368020303 -955234321 -845223250 -987030151 361884546 478030511 -746413161 223916271 -990378945 358822659 1 1 1 1 -366937206 1 -437629362 845645953 -472763508 1 1 1 -315077956...

output:

387516615933

result:

ok 1 number(s): "387516615933"

Test #17:

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

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

499999500000

result:

ok 1 number(s): "499999500000"

Test #18:

score: 0
Accepted
time: 332ms
memory: 12764kb

input:

1
1000000
-308212647 -654494679 -662770175 -369597654 -689669005 -453340797 -112978204 -284868951 -632329393 -854155790 -198771152 -695295095 -208518851 -279070810 -655433320 -15970181 -990391176 -173798333 -941455141 -221134289 -849477565 -755292789 -485310016 -404986409 -67746319 -533521433 -35504...

output:

0

result:

ok 1 number(s): "0"

Test #19:

score: 0
Accepted
time: 328ms
memory: 12324kb

input:

1
1000000
874536892 975675638 221164948 83153839 759842207 692180302 892515188 579157627 318968205 711042004 989098608 517293973 82540213 990771579 221431387 770613737 279546500 459636126 21707902 616965499 90954254 35950801 133603711 145086824 373754890 912955397 51309005 234304408 282479975 992094...

output:

0

result:

ok 1 number(s): "0"

Test #20:

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

input:

10000
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
4950
...

result:

ok 10000 numbers

Test #21:

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

input:

10000
100
-814534639 -777203811 -126367998 -408256921 -737043841 -435036017 -955631972 -813104283 -829440513 -134012773 -533980752 -851513460 -124198223 -503681096 -692671054 -246454414 -799756981 -924452892 -673387013 -755742463 -690068828 -359095650 -847832416 -510534736 -87954383 -727331660 -1367...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 10000 numbers

Test #22:

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

input:

10000
100
920983822 677750819 580784236 245649006 66394904 201663948 276763902 864002900 402836870 941700822 611178801 660939636 84602687 602212173 888365832 695104689 885542996 151256043 236020989 128878912 956843485 595870718 581445200 408534036 59670253 232310670 799764526 258670066 17055093 2550...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 10000 numbers

Test #23:

score: 0
Accepted
time: 342ms
memory: 11152kb

input:

1
1000000
-101901045 594761838 968622449 -458860311 757059432 -795596334 -358453396 384175376 517673829 901041494 84816584 76924692 -657142930 580682099 245650552 988227345 593043211 -164427362 832837177 -552339674 774111833 633249340 -110151576 868564965 335940945 8692426 -218219690 -743560001 7025...

output:

249999999600

result:

ok 1 number(s): "249999999600"

Test #24:

score: 0
Accepted
time: 210ms
memory: 11760kb

input:

1
1000000
87603641 1 1 519960971 183932229 1 1 316517655 1 664484124 780236393 1 1 419786746 1 1 1 782379659 656841598 1 122786135 273988086 359726922 1 1 1 1 691174343 11404687 1 586339934 67802870 1 692402653 296149865 927041143 77161538 1 1 1 1 1 490100945 1 122841477 1 1 763575783 1 122771131 23...

output:

375049744950

result:

ok 1 number(s): "375049744950"

Test #25:

score: 0
Accepted
time: 239ms
memory: 11948kb

input:

1
1000000
-942035994 1 -642722241 -285103286 -357147270 -586770049 1 1 1 -883225150 1 1 1 1 -652479132 1 1 1 1 1 -479756358 1 -563614866 1 1 1 -329844969 -967822758 1 -331458202 -88512127 -226650184 -301405352 -128885680 -336932385 -508419223 1 1 -457801545 -90401163 -4689586 -291951540 1 -28504337 ...

output:

374709081510

result:

ok 1 number(s): "374709081510"

Test #26:

score: -100
Wrong Answer
time: 155ms
memory: 3604kb

input:

100000
10
5 -7 -3 -6 0 -5 -10 -3 8 0
10
-7 -5 -1 -6 -3 -7 -7 -2 -6 6
10
-3 9 9 -6 10 4 10 3 0 4
10
3 -4 10 -9 -8 -8 1 -8 -4 3
10
4 10 9 5 -4 -3 7 8 0 -10
10
-3 -9 10 8 1 10 1 8 5 -9
10
0 9 -7 9 -2 -8 -4 -4 -4 3
10
-2 8 -5 -10 -6 5 -3 -7 -2 -6
10
-9 0 10 -4 1 -4 10 10 3 -6
10
9 -4 5 6 4 -6 -1 0 -3 -1...

output:

16
11
35
39
42
60
33
26
54
48
55
32
64
36
68
80
101
119
107
84
87
105
117
152
126
140
126
132
168
124
120
54
144
153
167
125
149
107
149
125
81
84
150
84
167
173
195
168
152
145
189
189
128
159
247
136
139
136
140
175
244
153
152
216
252
233
233
87
234
234
205
135
180
94
307
269
308
321
244
282
199
...

result:

wrong answer 2nd numbers differ - expected: '9', found: '11'