QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665156 | #5604. Triangle Containment | enze114514 | AC ✓ | 55ms | 13116kb | C++20 | 1.6kb | 2024-10-22 07:25:50 | 2024-10-22 07:25:51 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
struct Point {
int id, val;
int x, y;
};
int n, m;
int tr[N], idx[N];
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
int lowbit(int x) {
return x & -x;
}
int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void add(int x, int v) {
for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}
int Cross(Point A, Point B) {
return A.x * B.y - A.y * B.x;
}
int dis(Point A, Point B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
bool cmp(Point A, Point B) {
return Cross(A, B) > 0;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
vector<Point> q, p;
for (int i = 1; i <= n; i++) {
int x, y, v;
cin >> x >> y >> v;
q.pb({i, v, x, y});
p.pb({i, v, x - m, y});
}
sort(q.begin(), q.end(), cmp);
sort(p.begin(), p.end(), cmp);
for (int i = 0; i < n; i++) idx[p[i].id] = i + 1;
vector<int> ans(n + 1);
int cur = 0;
for (int i = 0; i < n; i++) {
int pos = q[i].id;
ans[pos] = cur - sum(idx[pos]);
add(idx[pos], q[i].val);
cur += q[i].val;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3864kb
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: 3852kb
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: 37ms
memory: 12680kb
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: 30ms
memory: 12552kb
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: 27ms
memory: 12392kb
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: 42ms
memory: 13116kb
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: 50ms
memory: 12820kb
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: 3636kb
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: 3868kb
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: 3684kb
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: 2ms
memory: 4188kb
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: 55ms
memory: 12304kb
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: 50ms
memory: 12276kb
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: 52ms
memory: 12860kb
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: 1ms
memory: 3808kb
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: 3648kb
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: 32ms
memory: 11888kb
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: 1ms
memory: 3832kb
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: 3648kb
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