QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#690881#5604. Triangle Containmentohiostatescarlet#AC ✓56ms12376kbC++172.2kb2024-10-31 07:33:202024-10-31 07:33:20

Judging History

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

  • [2024-10-31 07:33:20]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:12376kb
  • [2024-10-31 07:33:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

typedef tuple<ll,ll,ll,int> T;

struct Tree {
    typedef ll T;
    static constexpr T unit = 0;
    T f(T a, T b) { return a + b; } // (any associative fn )
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] += val; pos /= 2;)
        s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [ b , e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

ll cross(T&a, T&b) {
    auto [x1,y1,v1,i1] = a;
    auto [x2,y2,v2,i2] = b;
    return x1 * y2 - x2 * y1;
}

bool comp(T&a, T&b) {
    return cross(a, b) >= 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll n, w;
    cin >> n >> w;
    vector<T> valsA(n);
    vector<T> valsB(n);
    for (int i = 0; i < n; i++)
    {
        ll x, y, v;
        cin >> x >> y >> v;
        valsA[i] = {x, y, v, i};
        valsB[i] = {x-w, y, v, i};
    }
    sort(valsA.begin(), valsA.end(), comp);
    sort(valsB.begin(), valsB.end(), comp);

    vector<int> pos(n);
    for (int i = 0; i < n; i++)
    {
        if (i > 0 && cross(valsB[i-1], valsB[i]) == 0) {
            pos[get<3>(valsB[i])] = pos[get<3>(valsB[i-1])];
        } else {
            pos[get<3>(valsB[i])] = i;
        }
    }
    Tree t(n);
    int lastUpd = -1;
    vector<ll> res(n);
    for (int i = 0; i < n; i++) {
        int j = get<3>(valsA[i]);
        if (cross(valsA[lastUpd+1], valsA[i]) != 0) {
            for (int k = lastUpd+1; k < i; k++) {
                int j2 = get<3>(valsA[k]);
                t.update(pos[j2], get<2>(valsA[k]));
            }
            lastUpd = i-1;
        }
        res[j] = t.query(pos[j], n);
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 41ms
memory: 12228kb

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: 33ms
memory: 12376kb

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: 33ms
memory: 12220kb

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: 48ms
memory: 12372kb

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: 47ms
memory: 12216kb

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

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

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

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: 5ms
memory: 4356kb

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: 56ms
memory: 12224kb

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: 55ms
memory: 12220kb

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: 53ms
memory: 12372kb

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: 0
Accepted
time: 0ms
memory: 3788kb

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:

44212895086
27943726158
15759243040
41700014368
37646722985
28003347864
42427438300
7071675768
28362004104
39433718909
30737928694
3372752445
17284636535
25304653847
40749478994
13252328874
35841739554
2693811923
22961233110
31602054946
12387566714
37046360788
5941632966
17444101613
30036387817
3827...

result:

ok 100 lines

Test #16:

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

input:

100 1000000000
82 999999919 865563138
98 999999903 311192721
93 999999908 8429960
76 999999925 167143049
67 999999934 751184724
83 999999918 685990592
79 999999922 672959145
39 999999962 257382448
23 999999978 666297725
50 999999951 352746432
12 999999989 148667020
65 999999936 514415239
7 999999994...

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

result:

ok 100 lines

Test #17:

score: 0
Accepted
time: 38ms
memory: 12216kb

input:

100000 2
1 999900000 198886999
1 999900001 909793049
1 999900002 863164164
1 999900003 708106570
1 999900004 406194843
1 999900005 71117087
1 999900006 65335582
1 999900007 277160914
1 999900008 841061960
1 999900009 661275342
1 999900010 139661180
1 999900011 79477091
1 999900012 348464039
1 999900...

output:

0
198886999
1108680048
1971844212
2679950782
3086145625
3157262712
3222598294
3499759208
4340821168
5002096510
5141757690
5221234781
5569698820
6368907807
6587294368
7517457805
8188632279
8882767163
9858910365
10556640241
10859499817
11456754304
12443826668
12709335439
13647044755
14010232098
146609...

result:

ok 100000 lines

Test #18:

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

input:

100 1000000000
999999956 999999955 640799874
999999901 999999900 133031423
999999937 999999936 900146289
999999909 999999908 584368328
999999996 999999995 723061460
999999944 999999943 218414853
999999994 999999993 655128173
999999950 999999949 907767749
999999922 999999921 193614874
999999918 99999...

output:

26134037351
771068319
15753550289
4104845369
46653653478
20873842409
45689418749
23721269009
9350001321
7487757312
12827709421
41483551462
43271276481
19220535287
28239133766
16653696578
36296598137
12613652769
47376714938
30393634493
9543616195
41844239114
6819111265
44793861535
46344546922
9040997...

result:

ok 100 lines

Test #19:

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

input:

100 1000000000
999999961 999999962 864392047
999999989 999999990 609360020
999999935 999999936 157798603
999999984 999999985 755530427
999999957 999999958 929119464
999999934 999999935 968693315
999999967 999999968 772777020
999999974 999999975 671374074
999999906 999999907 278009743
999999914 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

result:

ok 100 lines