QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #319330 | #5604. Triangle Containment | chmpro | WA | 1055ms | 52912kb | Python3 | 609b | 2024-02-02 14:32:40 | 2024-02-02 14:32:40 |
Judging History
answer
import sys
input=sys.stdin.readline
F=lambda:[*map(int,input().split())]
N,X=F()
A=[]
for i in range(N):
x,y,v=F()
A.append((x,y,v,i)) #(x,y),가치,index
s1A=sorted(A,key=lambda a:a[0]/a[1])
s2A=sorted(A,key=lambda a:(a[0]-X)/a[1])
#print(A,s1A,s2A)
R2=[0]*N
for i in range(N):R2[s2A[i][3]]=i #A[i]는 2번째 기준으로 R2[i]등
SEGT=[0]*(2*N)
ANS=[0]*N
for _,_,v,i in s1A[::-1]:
l=N;r=R2[i]+N
while l<=r:
if l%2==1:ANS[i]+=SEGT[l]
if r%2==0:ANS[i]+=SEGT[r]
l=(l+1)//2
r=(r-1)//2
p=R2[i]+N
while p>=1:
SEGT[p]+=v
p>>=1
print(*ANS,sep='\n')
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 9964kb
input:
5 8 -8 1 1 -1 10 2 0 3 4 7 1 8 8 2 16
output:
0 12 0 0 8
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 9ms
memory: 10036kb
input:
6 6 0 1 1 2 3 10 2 5 100 3 1 1000 3 5 10000 4 5 100000
output:
0 1000 1010 0 1010 1000
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 720ms
memory: 35288kb
input:
99999 1000000000 500002962 1 1 500025469 1 1 500044229 1 1 500026049 1 1 499983663 1 1 499965983 1 1 499988191 1 1 499987116 1 1 500029240 1 1 499975570 1 1 499973295 1 1 499986404 1 1 500023312 1 1 499964976 1 1 499952153 1 1 500046927 1 1 499951857 1 1 499984523 1 1 500038724 1 1 499991318 1 1 500...
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 99999 lines
Test #4:
score: 0
Accepted
time: 663ms
memory: 48256kb
input:
100000 1000000000 -50000 1000000000 454290650 -49999 1000000000 208284433 -49998 1000000000 854275069 -49997 1000000000 627720731 -49996 1000000000 79147837 -49995 1000000000 614585061 -49994 1000000000 438660998 -49993 1000000000 300657551 -49992 1000000000 546865509 -49991 1000000000 353401129 -49...
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 100000 lines
Test #5:
score: 0
Accepted
time: 641ms
memory: 45088kb
input:
100000 1000000000 -1000000000 1 423302241 -999999999 1 941931570 -999999998 1 801255926 -999999997 1 434775469 -999999996 1 784636342 -999999995 1 41794758 -999999994 1 768189347 -999999993 1 746924545 -999999992 1 259101843 -999999991 1 798620683 -999999990 1 447243634 -999999989 1 848852324 -99999...
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 100000 lines
Test #6:
score: 0
Accepted
time: 761ms
memory: 48344kb
input:
99999 1000000000 499994038 499999999 998430190 500036272 499999997 789110725 499988970 499999999 119471973 500042096 499999996 855486238 499953314 499999995 464948333 499979222 499999999 573710457 500002347 499999999 385287206 500030797 499999998 589559003 500043266 499999996 394228619 500028049 499...
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 99999 lines
Test #7:
score: 0
Accepted
time: 1055ms
memory: 52792kb
input:
99999 1000000000 500015023 90276 306948325 499983944 103118 727377493 500025915 268634 390844401 499969478 372636 395763733 500025195 253915 906667281 500002248 2021 592484584 500028251 319247 781019435 500002485 2470 479698120 500019573 153240 55967591 499996332 5381 572934141 500029257 342388 5702...
output:
15051696338423 16078150983097 25952499356135 30563879765694 25230196738942 2259488216981 28303632160706 2499792223286 19602904344694 3673383395149 29316404847225 19221795418962 38250888335153 23679513945001 30552633725096 41032349094038 4706014608942 6009757248570 7122490953898 36599501815417 487970...
result:
ok 99999 lines
Test #8:
score: 0
Accepted
time: 17ms
memory: 9948kb
input:
10 288680785 178865786 867993864 636847607 -613161344 618644649 4263081 -334914334 835028097 479059864 398630267 451708968 198562303 686645136 168687978 165190276 -200168672 502489609 141287478 -883504351 181031707 365077741 -501817189 431943271 650129082 129731984 545411633 215780377 -908726401 301...
output:
215780377 0 141287478 0 0 0 0 0 0 0
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 13ms
memory: 9940kb
input:
100 862470218 144592658 795862025 180337071 610978659 337756758 825373184 -850415892 999708776 144412468 145639496 97986121 927151397 85876793 812422041 711017259 616720755 419591918 307077258 -922790633 387693386 638582277 -352105876 340345558 269560982 906901443 832999060 202790690 -287202723 1516...
output:
10307930450 4658004721 14031426378 1443001754 10134174850 8251060664 4098775963 6105870432 11911930052 0 10044436485 14256183211 12406409825 8806465381 5825191895 0 13952083201 1915181705 14031426378 4381226770 8806465381 3750624999 9206758205 13148122629 1468352473 11187120838 3859032409 1068054670...
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 10ms
memory: 10404kb
input:
1000 659772697 585462754 479471627 466753778 775503160 90740224 272218877 621373322 217587097 893441929 -822194651 147218893 73874310 981889424 850470009 958197874 -762306326 678405329 213676714 -737756885 462466755 885417330 914658434 322750488 349743526 165204318 24500837 103649345 -744652978 4040...
output:
32587805446 7776547057 18158011152 11781551446 66141686751 47723071741 34715681269 24663898378 1801916551 30837013147 55788717340 2286069297 52950906787 20365709900 44403147984 64981304643 41808750134 64529798428 19166153456 60332654759 0 34876625645 57630234591 66810907779 13599594173 32224973423 7...
result:
ok 1000 lines
Test #11:
score: 0
Accepted
time: 78ms
memory: 14188kb
input:
10000 990105539 -105315460 529252068 745036155 -5470163 401826492 159066781 -16798118 970083341 878975471 -60264629 132328742 261907070 129505467 458185750 425265815 -115292793 819596763 256231144 108458882 861508015 689927083 -630032289 733499695 510065999 -433769045 599754599 576036745 -374963400 ...
output:
643530424931 491670717373 1216895549184 168250718881 572916618018 1026202446956 1088773181772 907620348408 737525771296 437424166253 444719806363 583594040618 310263258530 833682773449 930565095073 936582072231 155076419050 276828755081 410235524340 813145065477 879409047261 906168023721 48129235867...
result:
ok 10000 lines
Test #12:
score: 0
Accepted
time: 900ms
memory: 52912kb
input:
100000 350465053 427679071 808257835 757678846 -467942346 507650682 861975896 839004548 296710810 89427992 17664263 444510777 450295615 48216050 597121388 552348457 -468271876 572418106 770209594 971937701 637879941 580107825 862765929 870420063 682238383 -419670166 39222434 585619481 664987835 2824...
output:
3533869421073 2281360493643 1251239475811 1925645240082 2634720624357 2543893149231 2748283007109 3675580747827 165468152091 1188648969217 1494896977939 3625312416315 2100940777144 2888131907602 2030206139719 1367133399021 121810540125 526614793042 1266970453648 2901614940406 693052561046 4891218683...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 896ms
memory: 52816kb
input:
100000 149249303 -809661990 255098420 228600344 -655754742 771673593 677687401 58946465 933824256 38254637 423602433 839510250 150333821 139839791 894897755 643399591 156828756 68450198 29132630 840053134 40696005 458034439 -447052327 375499977 263926384 378893901 428034798 725651935 -564346381 6124...
output:
483658126368 1457337311331 1735017472929 1597712363381 1689643982154 118432597102 68770946135 714464574333 815853234037 1168193603234 906619597894 1186041375386 370552422422 942225238623 1309031212634 152035694122 563698457428 213563404913 397154296484 1719601521304 616602688544 266552342851 1587413...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 784ms
memory: 48356kb
input:
100000 1 880573655 929915916 817935606 -900474181 751997605 723730335 -543556880 259982813 106140849 -220342922 648385147 887828651 642506165 287964053 102511718 -448263878 189158377 939720008 770174432 929073824 747393386 -486905952 73014930 102009041 -339212415 321227667 848913311 -365242600 10093...
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 100000 lines
Test #15:
score: -100
Wrong Answer
time: 12ms
memory: 10100kb
input:
100 1000000000 9 999999990 914094243 43 999999956 59621706 70 999999929 21719733 13 999999986 705431787 22 999999977 357218675 42 999999957 358656240 11 999999988 856909833 87 999999912 526476746 41 999999958 891142031 18 999999981 324744673 36 999999963 688252252 94 999999905 659632720 66 999999933...
output:
0 0 0 81341439 81341439 81341439 1502648141 0 966474425 2214835131 1857616456 0 1207829199 1316793067 4952017511 1186109466 4617851333 0 2343530759 6066867411 1865049988 7166750539 1338573242 3159832803 6687638362 8919448680 13283483729 1929647184 8340637843 0 2292427369 16389905526 4815242534 10112...
result:
wrong answer 1st lines differ - expected: '44212895086', found: '0'