QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#893265#10006. Good Trianglelgvc#AC ✓399ms17588kbC++231.5kb2025-02-10 16:58:382025-02-10 16:58:38

Judging History

This is the latest submission verdict.

  • [2025-02-10 16:58:38]
  • Judged
  • Verdict: AC
  • Time: 399ms
  • Memory: 17588kb
  • [2025-02-10 16:58:38]
  • Submitted

answer

#include <bits/stdc++.h>
int N,c1[500009],c2[500009],kk,sg[500009],tf[500009];
struct n_t{
    int x,y,c;
} f[500009];
bool cmp(n_t a,n_t b) {
    return a.x+a.y<b.x+b.y;
}
#define lb(x) ((x)&(-(x)))
void up(int p) {
    while(p<=N) {
        sg[p]++;
        p+=lb(p);
    }
}
inline int qr(int p) {
    int as=0;
    while(p) {
        as+=sg[p];
        p-=lb(p);
    }
    return as;
}
long long cl() {
    std::sort(f+1,f+N+1,cmp);
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
    for(int i=1;i<=N;i++) {
        tf[i]=f[i].x-f[i].y;
    }
    std::sort(tf+1,tf+N+1);
    for(int i=1;i<=N;i++) {
        f[i].c=std::lower_bound(tf+1,tf+N+1,f[i].x-f[i].y)-tf;
    }
    memset(sg,0,sizeof(sg));
    int p=0;
    for(int i=1;i<=N;i++) {
        while(p<N&&f[p+1].x+f[p+1].y<f[i].x+f[i].y) {
            p++;
            up(f[p].c);
        }
        c1[i]=qr(f[i].c-1);
    }
    memset(sg,0,sizeof(sg));
    long long ans=0;
    p=N+1;
    for(int i=N;i>=1;i--) {
        while(p>1&&f[p-1].x+f[p-1].y>f[i].x+f[i].y) {
            p--;
            up(N-f[p].c+1);
        }
        c2[i]=qr(N-f[i].c);
        ans+=1ll*c1[i]*c2[i];
    }
    return ans;
}
signed main(void) {
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d %d",&f[i].x,&f[i].y);
    }
    long long ans=1ll*N*(N-1)*(N-2)/6;
    ans-=cl();
    for(int i=1;i<=N;i++) std::swap(f[i].x,f[i].y);
    ans-=cl();
    printf("%lld",ans);
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 12824kb

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

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

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: 0ms
memory: 13552kb

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

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

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

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

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

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: 330ms
memory: 17588kb

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: 356ms
memory: 17484kb

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: 393ms
memory: 17376kb

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: 388ms
memory: 17580kb

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: 389ms
memory: 17584kb

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

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

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: 2ms
memory: 12092kb

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: 208ms
memory: 17584kb

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: 2ms
memory: 13760kb

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: 0ms
memory: 11924kb

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: 0ms
memory: 13576kb

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: 331ms
memory: 17584kb

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: 356ms
memory: 17588kb

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: 399ms
memory: 17584kb

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: 394ms
memory: 17584kb

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: 388ms
memory: 17420kb

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

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: 6ms
memory: 13636kb

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: 4ms
memory: 12992kb

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: 209ms
memory: 17580kb

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

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

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

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

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: 358ms
memory: 17580kb

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

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: 393ms
memory: 17584kb

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: 386ms
memory: 17580kb

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: 0ms
memory: 12032kb

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

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: 6ms
memory: 13412kb

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: 207ms
memory: 17460kb

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

input:

3
-1000000000 -1000000000
1000000000 1000000000
1000000000 -1000000000

output:

1

result:

ok 1 number(s): "1"