QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446173 | #8525. Mercenaries | ucup-team3924 | TL | 3399ms | 78724kb | C++20 | 5.7kb | 2024-06-16 23:13:26 | 2024-06-16 23:13:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct pt{
long long x, y;
bool operator<(const pt & p) const {
return tie(x, y) < tie(p.x, p.y);
}
bool operator==(const pt & p) const {
return tie(x,y) == tie(p.x, p.y);
}
pt operator + (const pt & p) const {
return pt{x + p.x, y + p.y};
}
pt operator - (const pt & p) const {
return pt{x - p.x, y - p.y};
}
long long cross(const pt & p) const {
return x * p.y - y * p.x;
}
long long cross(const pt & a, const pt & b) const{
return (a-*this).cross(b-*this);
}
};
long long det(const pt &a, const pt &b, const pt &c){
return a.cross(b, c);
}
int sgn(long long d){
return (d > 0) - (d < 0);
}
struct Line {
int a, b; long long c;
};
bool half(Line m){return m.a < 0 || (m.a == 0 && m.b < 0);};
bool operator<(Line m, Line n){
return make_pair(half(m), (long long)m.b * n.a) <
make_pair(half(n), (long long)m.a * n.b);
}
Line LineFromPoints(int x1, int y1, int x2, int y2) {
int a = y1 - y2, b = x2 - x1;
long long c = (long long)a * x1 + (long long)b * y1;
return {a, b, c}; // halfplane points to the l e f t of vec .
}
vector<pt>minkowski(const vector<pt> &P, const vector<pt> &Q){
int n = P.size(), m = Q.size();
vector<pt>res = {P[0] + Q[0]};
for(int i = 1, j = 1; i < n || j < m; ){
if(i < n && (j == m ||
(P[i] - P[i-1]).cross(Q[j] - Q[j-1]) < 0)){
res.push_back(res.back() + P[i] - P[i-1]);
++i;
} else {
res.push_back(res.back() + Q[j] - Q[j-1]);
++j;
}
}
return res;
}
vector<pt> merge(const vector<pt> &a, const vector<pt> &b){
vector<pt> res;
int n = a.size(), m = b.size();
int j = 0;
for(int i = 0; i < n; i++){
while(j < m && b[j] < a[i])res.push_back(b[j++]);
if(j < m && b[j] == a[i])continue;
res.push_back(a[i]);
}
while(j < m)res.push_back(b[j++]);
return res;
}
vector<pt>convexHull(vector<pt> P, bool sorted=false){
if(!sorted){
sort(P.begin(), P.end());
P.erase(unique(P.begin(), P.end()), P.end());
}
if(P.size() <= 1)return P;
vector<pt>ret;
for(auto p : P){
while(ret.size() > 0 && p.y >= ret.back().y)ret.pop_back();
while(ret.size() >= 2 && sgn(det(ret.end()[-2], ret.end()[-1], p)) > 0)ret.pop_back();
ret.push_back(p);
}
return ret;
}
pt bestie(const vector<pt> &hull, Line L){
int l = 0, r = hull.size()-1;
while(l <= r){
int m = (l + r)/2;
Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
if(M < L)r = m - 1;
else l = m + 1;
}
return hull[(l >= (int)hull.size()? l - 1: l)];
}
//vector<vector<pt>> items;
vector<vector<pt>> merc;
int n;
//void build_items(const vector<vector<pt>>&hulls, int v, int tl, int tr){
//if(tl == tr){
//items[v] = hulls[tl];
//} else {
//int tm = (tl + tr)/2;
//build_items(hulls, v*2, tl, tm);
//build_items(hulls, v*2 + 1, tm + 1, tr);
//items[v] = minkowski(items[v*2], items[v*2 + 1]);
//}
//}
const vector<pt>org = {pt{0, 0}};
struct SegTree{
vector<vector<pt>> items; int n;
SegTree(int n) : items(2 * n, org), n(n){}
void Update(int pos, const vector<pt>&hull){
for(items[pos += n] = hull; pos /= 2;)
items[pos] = minkowski(items[pos * 2], items[pos*2 + 1]);
}
vector<pt> sum(int b, int e) {
e++;
vector<pt>r1 = org, r2 = org;
for(b += n, e += n; b < e; b /= 2, e /= 2){
if(b%2) r1 = minkowski(r1, items[b++]);
if(e%2) r2 = minkowski(items[--e], r2);
}
return minkowski(r1, r2);
}
};
SegTree items(0);
//vector<pt> sum(int v, int tl, int tr, int l, int r) {
//if (l > r){
//return {pt{0,0}};
//}
//if (l == tl && r == tr) {
//return items[v];
//}
//int tm = (tl + tr) / 2;
//return minkowski(sum(v*2, tl, tm, l, min(r, tm)),
//sum(v*2+1, tm+1, tr, max(l, tm+1), r));
//}
void build_merc(const vector<pt>&mercenaries, int v, int tl, int tr){
if(tl == tr){
merc[v] = {mercenaries[tl]};
} else {
int tm = (tl + tr)/2;
build_merc(mercenaries, v*2, tl, tm);
build_merc(mercenaries, v*2 + 1, tm + 1, tr);
merc[v] = convexHull(merge(minkowski(merc[v*2], items.sum(tm+1, tr)), merc[v*2+1]), true);
}
}
bool check(const pt &p, const Line &L){
return ((long long)p.x * L.a + (long long)p.y * L.b) >= L.c;
}
int solve(int city, pt shift, const Line &L, int v, int tl, int tr, int l, int r){
//cout << v << ' ' << l << ' ' << r << '\n';
if(l > r){
return -1;
}
if(l == tl && r == tr){
if(!check(bestie(merc[v], L) + shift, L)){
//cout << "no mercenary in " << l << ' ' << r << " can beat the monster\n";
return -1;
}
if(tl == tr)return tl;
}
int tm = (tl + tr)/2;
int right = solve(city, shift, L, v*2+1, tm+1, tr, max(l, tm+1), r);
if(right != -1)return right;
//cout << "there is no mercenary in " << max(l, tm + 1) << ' ' << r << " that can win so i need to remove items: ";
//for(auto x : items.sum(max(l, tm+1), r))cout << x.x << ' ' << x.y << '\t';
//cout << '\n';
shift = shift + bestie(items.sum(max(l, tm+1), r), L);
return solve(city, shift, L, v*2, tl, tm, l, min(r, tm));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
//items.assign(4 * n, {pt{0, 0}});
merc.assign(4 * n + 1, {});
vector<pt> mercenaries(n);
vector<vector<pt>>hulls(n, {pt{0,0}});
for(int i = 0; i < n; i++){
cin >> mercenaries[i].x >> mercenaries[i].y;
if(i + 1 == n)break;
int r;
cin >> r;
vector<pt> pts(r);
for(auto &p : pts){
cin >> p.x >> p.y;
}
hulls[i + 1] = convexHull(pts);
}
items = SegTree(n);
items.Update(0, org);
for(int i = 1; i < n; i++)items.Update(i, hulls[i]);
build_merc(mercenaries, 1, 0, n-1);
int q;
cin >> q;
while(q--){
int v; int a, b;
long long c;
cin >> v >> a >> b >> c;
Line L{a, b, c};
int ans = solve(v, pt{0, 0}, L, 1, 0, n-1, 0, v-1);
cout << (ans == -1? -1 : ans + 1) << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3 1 1 2 1 2 1 2 3 2 5 1 5 4 3 3 4 5 1 1 2 4 5 12 1 1 1 1 2 1 1 1 3 1 1 1 3 1 1 9 3 2 2 20 3 1 2 18 3 1 2 19 3 1 2 20 3 0 1 8 2 1 0 4 2 1 0 3 2 1 0 2
output:
1 2 3 3 2 2 1 -1 1 -1 2 2
result:
ok 12 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
2 47 11 1 98 25 9 90 10 1 32 28 1811 2 17 44 4114 1 36 88 2661 2 79 33 3681 1 53 26 2778 2 59 20 2332 2 63 45 4616 2 72 11 10835 1 13 28 919 2 16 59 4445
output:
1 -1 -1 2 -1 1 2 1 1 2
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
3 87 42 5 69 12 82 79 10 88 45 51 40 3 18 6 5 73 100 58 41 40 88 54 5 40 98 31 63 100 3 32 13 1811 1 51 21 5318 1 32 5 2994 2 77 51 19184 2 78 60 1763 1 10 1 913 1 22 51 4057 1 2 5 385 2 50 15 989 2 65 53 1488 1 49 82 7708 2 33 90 1133 1 23 33 3388 1 92 36 9516 3 39 61 10014 2 43 55 1103 2 48 38 127...
output:
3 1 1 1 2 -1 -1 -1 2 2 -1 2 -1 1 2 2 -1 3 2 2 3 1 1 1 -1 1 1 1 3 1 -1 1 -1 1 2 1 2 1 1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 2 1 1 -1 2 -1 1 1 1 1 3 1 2 3 2 2 1 1 -1 1 1 3 1 1 1 3 2 1 1 2 1 2 1 2 1 -1 -1 -1 1 2 1 1 -1 -1 1 3 2 2
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 160ms
memory: 18812kb
input:
2 309248041 338995438 500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...
output:
2 1 -1 2 2 2 1 1 2 -1 2 2 1 1 2 1 2 2 1 2 2 1 -1 -1 1 -1 2 -1 1 2 1 1 1 1 -1 1 -1 -1 -1 1 2 2 1 1 1 2 -1 -1 1 -1 1 2 -1 1 2 1 2 2 -1 2 1 2 2 -1 2 2 -1 2 1 2 1 -1 -1 1 1 -1 2 1 2 2 1 1 1 1 2 2 -1 -1 1 2 2 -1 2 -1 -1 -1 1 2 1 1 2 2 1 -1 -1 2 2 2 1 -1 1 2 2 -1 1 -1 -1 -1 1 2 1 2 1 -1 -1 1 2 2 -1 2 2 2 ...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 457ms
memory: 78724kb
input:
200000 999999511 993051669 2 5000 5000 5000 5000 1000000000 1000000000 3 5000 5000 5000 5000 5000 5000 995868520 999999999 2 5000 5000 5000 5000 660478427 999992996 3 5000 5000 5000 5000 5000 5000 999999979 999999998 2 5000 5000 5000 5000 861450412 989532141 3 5000 5000 5000 5000 5000 5000 949861679...
output:
145800 198491 112658 29436 38091 122582 7727 87686 192036 97288 60184 836 39235 158331 121422 117149 189664 153018 181334 56603 69911 173097 165342 124250 103223 110099 177817 11459 37052 28918 57236 143793 19234 10313 75590 6597 18202 176357 102394 179685 5171 162359 72023 56758 88764 17257 100583 ...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
20 1538 3628 4 2423 3790 3127 3961 2614 3582 2016 4789 1441 276 3 2518 253 4221 265 3236 2574 1668 3370 4 4489 3533 4501 2177 1067 2337 2765 1480 1179 1926 3 4922 2537 1477 653 325 444 3964 2924 2 3415 4463 822 3257 210 4068 2 1969 167 1978 3712 2067 540 4 1560 2211 4050 4196 442 2279 442 2448 2962 ...
output:
5 14 5 1 2 3 6 -1 8 7 2 11 1 8 8 3 3 13 4 5
result:
ok 20 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
66 121 3727 2 1379 2036 975 1594 205 708 2 523 2978 176 2924 2528 440 4 3182 2078 1340 2166 1563 447 1076 157 3242 2859 5 2029 4660 2789 1593 4534 4137 921 3966 3440 1964 1503 3975 3 1354 3815 825 4981 1710 2692 858 2524 3 3395 3523 2184 4115 4043 3518 2610 731 3 3735 2799 442 1348 3101 2847 4306 14...
output:
9 12 20 -1 3 18 23 2 4 48 13 -1 8 38 8 28 7 1 8 51 4 9 10 10 3 24 14 5 19 2 33 3 45 5 4 29 5 23 24 36 24 -1 9 4 26 1 2 1 46 37 8 2 20 2 1 27 26 41 5 32 3 37 -1 7 43 2
result:
ok 66 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
200 2768 3191 1 482 2676 4032 1626 1 1313 472 117 4314 3 1745 3269 1723 1603 1307 2675 2553 172 5 1678 868 246 2764 3746 3346 3650 317 3675 3877 2425 2618 2 1883 4174 4213 1781 3099 3645 1 4652 2962 1910 1338 3 4530 2328 2576 3373 3 1145 1887 1331 4 459 736 139 3184 550 31 740 3134 3488 2965 3 2097 ...
output:
57 85 59 36 24 39 5 4 81 49 23 107 104 39 62 49 3 156 25 64 13 92 16 62 20 104 13 26 66 61 109 56 1 32 7 37 14 9 10 136 20 7 2 129 149 109 29 15 51 18 80 107 6 20 50 27 111 -1 115 16 10 88 21 12 88 1 2 31 72 10 67 68 5 6 1 80 120 73 187 26 17 2 64 125 -1 43 4 10 72 13 129 45 118 54 27 56 100 56 27 3...
result:
ok 200 numbers
Test #9:
score: 0
Accepted
time: 7ms
memory: 4044kb
input:
666 2648 877 2 170 1622 4953 3255 18 2631 2 2355 1545 3734 1505 724 216 1 1944 1090 3733 2918 3 3393 1081 3478 4932 2001 501 3399 1829 3 4189 4125 1957 1754 2904 3622 4643 554 4 229 4356 3777 1315 4848 2584 1232 2718 4096 1924 2 892 1180 3500 2905 1759 1274 4 3950 1096 1779 2159 1617 1856 3182 2679 ...
output:
466 198 247 228 66 306 101 147 11 480 35 354 59 225 76 20 314 84 272 2 315 13 6 4 212 430 28 290 339 121 125 4 21 362 254 19 77 456 69 27 62 6 269 100 68 4 396 1 58 377 203 100 94 162 188 151 48 4 377 277 242 274 217 167 45 24 116 291 263 305 112 183 225 5 107 120 210 56 50 140 4 192 165 250 303 77 ...
result:
ok 666 numbers
Test #10:
score: 0
Accepted
time: 39ms
memory: 4932kb
input:
2000 2883 1742 3 281 1763 9 3931 3350 1572 1611 462 3 983 1286 1874 1928 4279 857 3773 1341 2 3861 4264 733 4060 1220 1451 3 2753 624 4520 2881 2051 1614 1406 2742 5 2857 2152 4349 495 3552 1319 4118 4269 3286 2235 4028 1138 4 2209 4188 1788 4226 517 2932 4067 3746 3105 2345 2 731 2039 1927 1275 137...
output:
1 210 42 101 386 26 68 202 806 352 362 29 559 52 1334 741 260 565 1041 85 220 67 448 194 1110 179 843 625 453 1055 641 691 79 145 869 10 40 8 60 134 1108 179 560 773 1748 452 469 1165 515 456 602 366 781 15 5 269 459 42 509 1046 339 1064 923 944 84 76 499 -1 1345 1051 44 2 1406 680 1726 326 32 96 85...
result:
ok 2000 numbers
Test #11:
score: 0
Accepted
time: 368ms
memory: 7856kb
input:
6666 2741 2461 3 526 4139 3060 2030 2766 3316 653 3631 1 4366 67 2628 3849 2 2449 2607 1617 68 3001 126 1 4561 4505 3166 3358 3 4322 1581 957 756 865 3540 1442 2226 4 4137 2789 2636 3371 3383 60 620 2488 550 3026 5 1285 3936 4074 4144 3933 3572 825 2255 55 796 4544 1791 3 1459 863 4284 3153 1674 122...
output:
46 1772 1912 2973 15 5358 3822 649 679 4265 1819 3808 783 1759 1426 2865 1820 11 168 209 4207 3606 1234 4049 576 1052 1514 86 191 712 4475 2262 223 1513 3483 3719 5287 4028 200 2063 241 1217 3043 622 955 5463 1806 337 855 2275 2962 164 3955 1673 353 2999 4622 2701 601 1999 933 35 2004 3380 64 776 27...
result:
ok 6666 numbers
Test #12:
score: 0
Accepted
time: 3399ms
memory: 18384kb
input:
20000 1186 1182 1 2552 75 370 1750 2 1657 2841 3265 719 3481 2197 2 4047 16 277 1224 593 97 4 358 4602 1995 1679 1888 4757 4297 2320 3187 3062 2 2394 2756 3744 3166 467 261 3 3385 2572 4595 719 3514 1870 178 3985 4 1004 1799 4259 2920 1155 2664 4064 3732 385 2278 2 1784 4561 1022 1281 3907 2706 1 39...
output:
629 10461 7163 711 6127 3895 1990 1492 3117 2779 3930 428 10729 938 1012 541 6697 3517 4567 6669 285 10601 15453 11721 2 633 535 288 13293 15510 13541 1550 6895 6138 5565 6672 93 1621 6958 4345 4669 6546 11999 74 4152 7192 3334 2423 1982 1884 1956 3630 4614 1777 1826 6986 9 2318 8064 303 3082 1287 1...
result:
ok 20000 numbers
Test #13:
score: -100
Time Limit Exceeded
input:
40000 1322 4123 3 1729 4107 1325 1826 756 1338 2281 2223 4 3251 2045 4210 3298 3405 2626 2449 2539 332 4779 2 4329 2666 4605 253 501 2829 3 2908 2017 3694 4704 3794 3259 2231 3518 3 984 1800 2861 888 1137 4675 16 2796 5 3690 143 3763 3138 663 298 174 2769 3953 1526 1320 1584 2 3472 4857 1781 4871 39...