QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884196#10006. Good TriangleKevin5307AC ✓423ms42872kbC++231.8kb2025-02-05 22:02:272025-02-05 22:02:27

Judging History

This is the latest submission verdict.

  • [2025-02-05 22:02:27]
  • Judged
  • Verdict: AC
  • Time: 423ms
  • Memory: 42872kb
  • [2025-02-05 22:02:27]
  • Submitted

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n;
ll x[500500],y[500500];
ll v1[500500],v2[500500],v3[500500],v4[500500];
ll bit[500500];
void update(int p,ll v)
{
	while(p<500500)
	{
		bit[p]+=v;
		p+=(p&(-p));
	}
}
ll query(int p)
{
	ll ans=0;
	while(p)
	{
		ans+=bit[p];
		p-=(p&(-p));
	}
	return ans;
}
void solve(ll *V1,ll *V2)
{
	memset(bit,0,sizeof(bit));
	int p=0;
	vector<int> vind;
	for(int i=1;i<=n;i++)
		vind.pb(i);
	sort(ALL(vind),[&](int u,int v){return y[u]<y[v];});
	for(auto ind:vind)
	{
		while(p<sz(vind)&&y[vind[p]]<y[ind])
		{
			update(x[vind[p]],1);
			p++;
		}
		V1[ind]=query(x[ind]-1);
		V2[ind]=query(n)-query(x[ind]);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	vector<ll> px,py;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		ll a=x[i]+y[i];
		ll b=x[i]-y[i];
		x[i]=a;
		y[i]=b;
		px.pb(a);
		py.pb(b);
	}
	srt(px);
	uni(px);
	srt(py);
	uni(py);
	for(int i=1;i<=n;i++)
	{
		x[i]=ub(px,x[i]);
		y[i]=ub(py,y[i]);
	}
	solve(v1,v2);
	for(int i=1;i<=n;i++)
		y[i]=sz(py)+1-y[i];
	solve(v3,v4);
	ll ans=1ll*n*(n-1)*(n-2)/6;
	for(int i=1;i<=n;i++)
		ans-=v1[i]*v4[i]+v2[i]*v3[i];
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 -1
1 5
5 7
1 3
4 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

10
-2 -1
-2 2
-1 -2
-1 -1
-1 1
0 1
1 -1
1 2
2 -1
2 1

output:

108

result:

ok 1 number(s): "108"

Test #3:

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

input:

8
-5353885 177168259
393803106 -221988732
517220368 -345405994
143143400 28670974
-179553118 351367492
447166616 -275352242
-72145562 243959936
-274698525 446512899

output:

56

result:

ok 1 number(s): "56"

Test #4:

score: 0
Accepted
time: 1ms
memory: 19360kb

input:

8
-324947127 116858935
372954148 -81124978
54845173 -262933365
122995467 -331083659
-350010483 641839653
-599969164 391880972
-74988446 366817616
-73250266 365079436

output:

56

result:

ok 1 number(s): "56"

Test #5:

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

input:

10
157433098 -150486510
741495015 -58558849
860039937 59986073
613972809 306053201
403500226 -396553638
68842013 -239077595
314909141 -485144723
-24746679 -332666287
221320449 -578733415
495427887 187508279

output:

120

result:

ok 1 number(s): "120"

Test #6:

score: 0
Accepted
time: 2ms
memory: 19660kb

input:

9
179264487 -544344907
139756831 -583852563
481689324 -241920070
223597013 -500012381
828224017 104614623
14865396 -708743998
89252586 -634356808
475703232 -247906162
301875222 -421734172

output:

84

result:

ok 1 number(s): "84"

Test #7:

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

input:

10
-623065093 198755267
-368090840 -393092046
225795796 409211766
-93406399 728413961
372178992 555594962
52976797 874797157
-303862898 -120446928
-472299428 -288883458
-791501623 30318737
476387580 451386374

output:

114

result:

ok 1 number(s): "114"

Test #8:

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

input:

8
-436280563 40679439
68302509 -89073311
-52148970 471776818
589381280 336967420
34530786 385097062
-248865402 228094600
-333757066 143202936
-119112652 -276488472

output:

49

result:

ok 1 number(s): "49"

Test #9:

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

input:

10
-477236362 165824920
188776620 -500188062
-8340601 577345567
662040674 -93035708
-159868135 425818033
78314899 664001067
497779358 -191185324
-123585922 462100246
-60356350 802672316
184430545 648794743

output:

106

result:

ok 1 number(s): "106"

Test #10:

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

input:

499998
-12023827 330263227
-664373810 24735206
305768212 -67930490
368765325 213424915
33206371 919185805
-647540955 191952141
355341003 -524613427
539454004 145694368
-404535204 559105834
-740702365 168088895
-149191340 -73936930
195872405 -752246739
34365000 -408325744
576078603 -102167279
4304638...

output:

13931045633752587

result:

ok 1 number(s): "13931045633752587"

Test #11:

score: 0
Accepted
time: 300ms
memory: 42792kb

input:

500000
517325606 -199260210
115196805 -56572125
281056762 -433461176
-161659966 498283130
-391924031 464800253
766549774 174283342
525457342 344241686
-246618483 84917847
39189914 -322670742
262995692 696558940
-560096113 -5709187
368102396 553155380
261954520 -636827658
-12851107 -877034845
5250120...

output:

13895596871211648

result:

ok 1 number(s): "13895596871211648"

Test #12:

score: 0
Accepted
time: 385ms
memory: 42868kb

input:

500000
-133502744 -90507140
646933552 219286468
-373613434 -504884618
-343025188 -595434664
-8003492 -638812988
-685998945 -46092109
341647783 -584356157
91652618 907982040
17995628 39810530
498261616 476740824
-852365722 -106180910
-294452584 -467043076
-244926348 -342666982
-532774098 -96117142
-8...

output:

13891775451269110

result:

ok 1 number(s): "13891775451269110"

Test #13:

score: 0
Accepted
time: 408ms
memory: 42864kb

input:

499999
114506099 -246676185
-459593763 388129679
297744224 -342595828
-817717759 -100918027
495509096 -412787144
245090361 -611617455
105906132 -306778712
-253921556 -217999540
593744189 -394716307
56313297 70718451
-647640628 -149060026
-658297766 54530742
343875812 -414202580
-559349589 -68020201
...

output:

13885578636476121

result:

ok 1 number(s): "13885578636476121"

Test #14:

score: 0
Accepted
time: 419ms
memory: 42868kb

input:

499998
125744151 -450232279
-600722706 356800788
-517315437 302443511
130795521 234400367
555475526 236342596
-190901050 586825122
-227691638 -139374086
517388093 1592767
-664085466 -191643176
390306640 593384378
280422726 219378472
-322113133 191283935
726764465 212908491
-754519643 244082977
-2449...

output:

13891247749090827

result:

ok 1 number(s): "13891247749090827"

Test #15:

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

input:

10
-2 -2
-1 -3
-1 -1
-2 -3
-1 1
-2 1
-1 -2
-2 0
-2 -1
-1 0

output:

82

result:

ok 1 number(s): "82"

Test #16:

score: 0
Accepted
time: 5ms
memory: 18228kb

input:

9999
50 3
60 -9
-10 19
16 29
54 12
-36 85
27 10
12 59
-32 -1
20 -4
42 1
55 52
27 84
-22 61
53 -5
52 84
9 31
-18 22
51 47
13 42
13 90
54 84
-6 24
55 50
-29 16
27 -6
5 63
-11 58
-16 -1
45 44
17 55
-10 87
16 45
-13 77
34 10
55 77
59 29
-23 0
-10 2
59 75
9 23
-36 17
13 41
52 90
11 74
-25 60
-21 21
-25 7...

output:

121482420921

result:

ok 1 number(s): "121482420921"

Test #17:

score: 0
Accepted
time: 5ms
memory: 21332kb

input:

9998
-66 23
-43 -3
-63 17
-76 29
-17 11
44 28
21 -3
-92 -16
-21 13
71 -15
-62 21
11 13
-84 -5
-4 10
-105 -15
-46 -6
84 26
-51 -9
-103 10
-4 -12
-56 2
-43 27
-47 -6
49 -7
70 -12
17 1
-95 10
-93 -14
41 6
-108 6
-89 -18
62 5
42 -14
-59 28
67 23
21 13
76 3
-64 3
-3 4
-86 17
74 -8
73 -10
-24 18
46 -6
63 ...

output:

66983215340

result:

ok 1 number(s): "66983215340"

Test #18:

score: 0
Accepted
time: 392ms
memory: 42872kb

input:

499999
-691836 661884688
-2436 505317808
-1161096 -730434632
-1171594 -235603628
-1301917 -440281561
-55737 878513579
-1020033 -302111631
-612334 -862337634
-27759 525559643
-1109391 22891985
-685524 151691948
-110298 487560846
-1075735 -523361837
-1259798 -264279164
-884836 -60690392
-1249007 -2237...

output:

0

result:

ok 1 number(s): "0"

Test #19:

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

input:

9
-174859413 67479603
-165982926 -750447504
-64675724 -649140302
-409704313 -506726117
-579384723 -337045707
373683278 616022294
-308397111 -405418915
238542384 -345922194
543363688 446341884

output:

81

result:

ok 1 number(s): "81"

Test #20:

score: 0
Accepted
time: 1ms
memory: 19024kb

input:

9
-30505280 -96692436
-352066529 224868813
18703576 395807198
-81212284 495723058
133498126 510601748
-628575696 -51640354
355143515 288956359
356225648 58285126
646938732 109317308

output:

68

result:

ok 1 number(s): "68"

Test #21:

score: 0
Accepted
time: 1ms
memory: 18156kb

input:

8
-6252574 926145266
-3251628 292749178
793627698 -177205438
474299239 348561843
624436646 -334939096
553235754 427498358
24168136 956565976
263430138 559430944

output:

48

result:

ok 1 number(s): "48"

Test #22:

score: 0
Accepted
time: 268ms
memory: 42864kb

input:

500000
-25426352 -523741786
-524917184 -27267878
129252045 111623837
-56741756 -100069842
-124854449 871500355
-166033088 700908754
-121420344 537816864
576876704 -54525192
683761081 27492447
244658809 -687059053
-179696382 -182849328
747616040 -970134
20122152 -861423358
-112425060 498441880
-21407...

output:

13931932690968428

result:

ok 1 number(s): "13931932690968428"

Test #23:

score: 0
Accepted
time: 309ms
memory: 42872kb

input:

499998
-361093233 280354011
213909100 66923890
23012067 -177712969
852739484 51954774
-489026011 -213002691
-649547359 295397785
-610097861 -315086587
224760452 623080324
515103844 -401155764
-708615480 -114987500
-19640920 347384418
-596944985 139194989
-835517532 -121723026
841202967 -126650761
-3...

output:

13893628573079030

result:

ok 1 number(s): "13893628573079030"

Test #24:

score: 0
Accepted
time: 389ms
memory: 42868kb

input:

499998
66027824 -607714988
53807202 -316330396
282896796 -393807218
17013651 -366155989
9063681 -273699961
-161526210 -183229200
-145519626 632934318
677452438 -6442652
375483956 367699366
402180648 -123017642
-521027263 68458745
136684004 790281014
-208899564 350981464
-185021085 558396449
44858009...

output:

13886867726622665

result:

ok 1 number(s): "13886867726622665"

Test #25:

score: 0
Accepted
time: 411ms
memory: 42868kb

input:

499998
261393864 703423492
675210021 -242296107
-363522149 -186495859
-524364828 -382482540
644352547 -76231155
-229199368 -392581852
-489412518 -133309098
-43716180 434314262
905404565 -68028673
-242434008 328258572
-330784787 435947511
-322563656 138145322
-620240082 120873868
433259558 290481336
...

output:

13893139257743113

result:

ok 1 number(s): "13893139257743113"

Test #26:

score: 0
Accepted
time: 420ms
memory: 42840kb

input:

499999
730787802 237525976
43914682 -949957808
84930346 654460864
-194218476 118506516
246511246 -232489584
160234390 543207570
-319654366 366871836
-233340343 593495633
495673669 -57650069
-572811208 161673736
544562411 -334344335
-104534508 -437879466
787604741 11330803
618707496 -348702306
-62400...

output:

13890046508710202

result:

ok 1 number(s): "13890046508710202"

Test #27:

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

input:

8
-2 -3
-1 -3
-2 0
-2 -4
-1 0
-2 -1
-1 -1
-2 -2

output:

38

result:

ok 1 number(s): "38"

Test #28:

score: 0
Accepted
time: 2ms
memory: 18896kb

input:

10000
-5 67
6 53
7 -2
-3 35
-8 57
40 -13
58 33
15 50
-8 -19
68 44
64 57
37 50
55 -16
26 -1
31 -21
21 -15
45 25
65 39
43 53
17 44
15 -17
-11 8
4 13
-24 67
36 64
45 56
61 2
-19 1
-21 -6
36 34
45 15
38 -2
61 32
-19 71
67 60
-15 0
2 35
4 48
-23 25
27 -13
-29 24
43 -15
65 58
64 43
-22 -23
30 50
39 -23
39...

output:

121516554520

result:

ok 1 number(s): "121516554520"

Test #29:

score: 0
Accepted
time: 3ms
memory: 18888kb

input:

9999
-34 -19
-145 -35
-134 -13
-130 -35
-30 -35
-95 -39
-170 -21
-159 0
-79 -35
-15 -19
11 -27
-79 -37
15 -9
-51 -2
-115 4
-62 -34
-177 -31
-87 -13
-123 -22
-1 -23
-120 -27
-154 4
-137 -21
-15 -28
-8 2
-106 -11
-4 1
-47 1
-112 -37
-125 -5
-109 -12
-143 -44
-43 5
-19 -24
-38 -15
-25 -9
-138 3
-166 -3...

output:

67008499120

result:

ok 1 number(s): "67008499120"

Test #30:

score: 0
Accepted
time: 396ms
memory: 42844kb

input:

499998
-180036999 466647
546376895 -274191
-759132786 -571704
13462383 52379
999043121 6901
-671182806 -659244
-76720384 225530
531060421 -359935
407711301 98395
300237205 -145349
885976725 -608093
319681738 -29924
742182593 -891785
897909385 -474679
-177003169 275039
304424945 68603
849887326 -6715...

output:

0

result:

ok 1 number(s): "0"

Test #31:

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

input:

10
166026482 832001424
663929201 334098705
-229711492 -559541988
802071362 195956544
543275974 213445478
45373255 711348197
-727614211 -61639269
-91569331 -697684149
-75571576 -405402072
62570585 -543544233

output:

114

result:

ok 1 number(s): "114"

Test #32:

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

input:

8
42216117 616406995
261826201 -692170641
-502267659 71923219
-695544180 265199740
-185570643 775173277
190485873 -105532847
976662583 22665741
19292202 980036122

output:

47

result:

ok 1 number(s): "47"

Test #33:

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

input:

9
137895386 -652297896
381226682 218530664
-69114208 -320192944
177268437 -691670947
419323155 -449616229
39671460 -80573048
229796057 67100039
85119104 -474426256
-149865795 -400944531

output:

70

result:

ok 1 number(s): "70"

Test #34:

score: 0
Accepted
time: 269ms
memory: 42812kb

input:

499998
-148514130 410127030
250777101 -479766821
-812093982 168158934
-88612015 -639230131
68254368 -144790976
734310736 -18352106
285771591 -620516891
133941470 272937488
-502271425 490173839
374285063 -577804317
-124732179 371216877
599201819 302132777
-597450071 -351285685
873607299 -46502577
339...

output:

13928026996625138

result:

ok 1 number(s): "13928026996625138"

Test #35:

score: 0
Accepted
time: 303ms
memory: 42872kb

input:

499998
-63878687 541097821
-111901249 239040699
-94270400 -305664352
87612771 -828053845
302553604 -428878366
-923276410 44701774
37376350 -715736772
576720958 -365080298
32991904 214541942
524286493 -385837495
579260791 375887417
195849822 444241664
81124173 -533021023
22202479 144972063
443313611 ...

output:

13892975848363715

result:

ok 1 number(s): "13892975848363715"

Test #36:

score: 0
Accepted
time: 388ms
memory: 42800kb

input:

500000
122345378 -664770190
-616980514 296674848
-236533972 106847166
32382348 327652874
-604867541 244889835
-577136105 -280507737
-22739297 128055825
-202654251 -245241277
482413205 -214166729
-157869444 -400132254
783515682 178921548
378718057 -7780653
-584128028 -111442438
-735997571 45284331
61...

output:

13887183745220121

result:

ok 1 number(s): "13887183745220121"

Test #37:

score: 0
Accepted
time: 417ms
memory: 42868kb

input:

499999
148830873 -307392609
326861376 72049242
593104343 197958519
434990026 -455784390
102364252 -865514648
-262468945 -326648063
378236658 -144223794
188690223 -690564795
-721613891 118344189
-155750053 -417651461
-196281065 153294409
-376168434 268878858
809426324 165442886
143479414 78279418
227...

output:

13889858915641519

result:

ok 1 number(s): "13889858915641519"

Test #38:

score: 0
Accepted
time: 423ms
memory: 42872kb

input:

500000
-430724925 -99811915
152068662 -600097074
-752223403 -45302629
-10099387 -791672445
8403405 -331379707
94985137 -22062303
-953244323 40557901
533689968 -16458830
68264974 -656280234
-397217458 -451079316
364445912 499169738
945188900 -39167816
-71949252 305342578
-682501076 232577472
14790596...

output:

13887844643863157

result:

ok 1 number(s): "13887844643863157"

Test #39:

score: 0
Accepted
time: 2ms
memory: 19384kb

input:

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

output:

59

result:

ok 1 number(s): "59"

Test #40:

score: 0
Accepted
time: 4ms
memory: 19952kb

input:

9999
10 -19
-34 -8
23 -50
-53 -5
-61 0
-45 -20
23 -66
-20 -50
-31 -78
16 1
-11 -84
5 -85
-43 -35
-27 9
-60 4
-34 -20
-64 -26
-14 -7
4 -86
-15 -5
-40 -33
15 -51
9 9
-31 -29
-65 -25
-31 -28
-35 -71
7 -77
10 -33
-15 0
-6 -83
-17 -28
-2 -45
-31 1
-21 -26
-21 -35
5 -19
-57 -48
-61 -29
9 -71
-62 3
17 -64
...

output:

121481280579

result:

ok 1 number(s): "121481280579"

Test #41:

score: 0
Accepted
time: 5ms
memory: 18408kb

input:

10000
-41 37
68 36
84 25
110 26
136 47
70 42
9 -1
-31 41
1 28
128 5
113 46
43 39
109 45
-45 1
126 4
63 17
16 34
54 8
3 39
3 47
96 43
5 36
88 31
133 0
41 16
150 8
103 8
47 34
107 33
-3 8
-25 37
23 9
6 28
114 17
101 42
-29 32
50 44
-5 24
122 36
79 33
46 26
37 12
50 39
13 25
125 37
69 25
70 32
62 5
14 ...

output:

67026289220

result:

ok 1 number(s): "67026289220"

Test #42:

score: 0
Accepted
time: 395ms
memory: 42868kb

input:

499999
-467239570 861530
643458011 245447
540413402 -13838
775301546 801248
120750071 848871
-877898425 1061207
-778122046 1079264
-236262370 1406128
669451423 279833
698046858 468404
12907820 860420
519581359 -158595
146217574 867502
85040477 623709
394808799 157743
-74674947 754105
-122437943 1048...

output:

0

result:

ok 1 number(s): "0"

Test #43:

score: 0
Accepted
time: 1ms
memory: 19196kb

input:

3
-1000000000 -1000000000
1000000000 1000000000
1000000000 -1000000000

output:

1

result:

ok 1 number(s): "1"