QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461559 | #8525. Mercenaries | charchach | WA | 338ms | 180124kb | C++14 | 6.1kb | 2024-07-02 20:19:52 | 2024-07-02 20:19:53 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#define LL long long
#include<vector>
using namespace std;
const int N = 5e5 + 9;
struct vec
{
LL x, y;
vec operator - (const vec& X)const
{
return {x - X.x, y - X.y};
}
vec operator + (const vec& X)const
{
return {x + X.x, y + X.y};
}
}a[N], A[N], B[N], C[N];
LL crs(vec a, vec b)
{
return a.x * b.y - a.y * b.x;
}
vector < vec > road[N];
vec st[N];
bool cmp(vec a, vec b)
{
return (a.x != b.x) ? a.x < b.x : a.y < b.y;
}
struct hull
{
vector < vec > p;
friend hull operator + (const hull& a, const hull& b)
{
if (!a.p.size())
return b;
if (!b.p.size())
return a;
hull r;
int n1 = 0, n2 = 0;
for (vec x : a.p)
A[++ n1] = x;
for (vec x : b.p)
B[++ n2] = x;
vec O = A[1] + B[1];
-- n1, -- n2;
for (int i = n1 - 1;i >= 1;-- i)
A[i] = A[i + 1] - A[i];
for (int i = n2 - 1;i >= 1;-- i)
B[i] = B[i + 1] - B[i];
int n = 0, i = 1, j = 1;
while (n < n1 + n2)
{
if ((j > n2) || (i <= n1 && crs(A[i], B[j]) > 0))
C[++ n] = A[i ++];
else
C[++ n] = B[j ++];
}
r.p.push_back(O);
C[0] = O;
for (int i = 1;i <= n;++ i)
C[i] = C[i] + C[i - 1], r.p.push_back(C[i]);
return r;
}
friend hull operator ^ (const hull& a, const hull& b)
{
if (!a.p.size())
return b;
if (!b.p.size())
return a;
hull r;
int n = 0;
for (vec x : a.p)
A[++ n] = x;
for (vec x : b.p)
A[++ n] = x;
sort(A + 1, A + 1 + n, cmp);
int top = 0;
for (int i = 1;i <= n;++ i)
{
while (top > 1 && crs(A[i] - st[top], st[top] - st[top - 1]) <= 0)
-- top;
st[++ top] = A[i];
}
for (int i = 1;i <= top;++ i)
r.p.push_back(st[i]);
return r;
}
LL get(int i, LL x, LL y)
{
return p[i].x * x + p[i].y * y;
}
LL ask(LL x, LL y)
{
int l = 0, r = (int)p.size() - 1;
// fprintf(stderr, "binary search:%d %d %lld %lld\n", l, r, x, y);
if (r < l)
return 0;
while (r - l > 10)
{
int P = (l + r) >> 1, Q = P + 1;
if (get(P, x, y) > get(Q, x, y))
r = Q;
else
l = P;
}
LL ans = get(l, x, y);
for (int i = l;i <= r;++ i)
ans = max(ans, get(i, x, y));
return ans;
}
};
hull makehull(const vector < vec >& p)
{
return {p};
}
vector < vec > makevector(vec p)
{
vector < vec > r;
r.push_back(p);
return r;
}
struct node
{
int l, r;
hull a, b;
friend node operator + (const node& a, const node& b)
{
return {a.l, b.r, (a.a + b.b) ^ b.a, a.b + b.b};
}
}tr[N << 2];
#define ls (p << 1)
#define rs ((p << 1) | 1)
void bd(int l, int r, int p = 1)
{
int mid = (l + r) >> 1;
if (l == r)
tr[p] = {l, r, makevector(a[l]), makehull(road[l])};
else
bd(l, mid, ls), bd(mid + 1, r, rs), tr[p] = tr[ls] + tr[rs];
// fprintf(stderr, "%d %d\n", l, r);
// for (vec x : tr[p].a.p)
// fprintf(stderr ,"%lld %lld\n", x.x, x.y);
// fprintf(stderr, "\n");
// for (vec x : tr[p].b.p)
// fprintf(stderr ,"%lld %lld\n", x.x, x.y);
// fprintf(stderr, "\n---------------------\n\n\n");
}
int ans;
void Ask(LL x, LL y, LL c, int p)
{
int l = tr[p].l, r = tr[p].r;
if (r < ans)
return;
if (l == r)
{
// fprintf(stderr, "%d %d\n", l, r);
if (tr[p].a.ask(x, y) >= c)
ans = max(ans, l);
// fprintf(stderr, "%d %d\n", l, r);
return;
}
if (tr[rs].a.ask(x, y) >= c)
Ask(x, y, c, rs);
else
Ask(x, y, c - tr[rs].b.ask(x, y), ls);
}
LL ask(int sl, int sr, LL x, LL y, LL c, int p = 1)
{
int l = tr[p].l, r = tr[p].r, mid = (l + r) >> 1;
// fprintf(stderr, "%d %d %d %d\n", sl, sr, l, r);
if (l >= sl && r <= sr)
{
// fprintf(stderr, "start:%d %d %d %d %lld %lld %lld\n", sl, sr, l, r, x, y, c);
Ask(x, y, c, p);
// fprintf(stderr, "end:%d %d %d %d %lld %lld %lld\n", sl, sr, l, r, x, y, c);
return tr[p].b.ask(x, y);
}
LL res = 0;
if (sr > mid)
res = ask(sl, sr, x, y, c, rs);
if (sl <= mid)
{
LL r = ask(sl, sr, x, y, c - res, ls);
res += r;
}
return res;
}
int main()
{
int n, m;
scanf("%d", &n);
scanf("%lld%lld", &a[1].x, &a[1].y);
for (int i = 2;i <= n;++ i)
{
int m;
scanf("%d", &m);
for (int j = 1;j <= m;++ j)
{
vec v;
scanf("%lld%lld", &v.x, &v.y), road[i].push_back(v);
}
sort(road[i].begin(), road[i].end(), cmp);
int top = 0;
for (vec x : road[i])
{
while (top && st[top].y <= x.y)
-- top;
st[++ top] = x;
}
road[i].clear();
for (int j = 1;j <= top;++ j)
road[i].push_back(st[j]);
top = 0;
for (vec x : road[i])
{
while (top > 1 && crs(x - st[top], st[top] - st[top - 1]) <= 0)
-- top;
st[++ top] = x;
}
road[i].clear();
for (int j = 1;j <= top;++ j)
road[i].push_back(st[j]);
scanf("%lld%lld", &a[i].x, &a[i].y);
}
bd(1, n);
scanf("%d", &m);
for (LL a, b, c;m --;)
{
int i;
scanf("%d%lld%lld%lld", &i, &a, &b, &c);
ans = -1;
ask(1, i, a, b, c);
printf("%d\n", ans);
// fprintf(stderr, "%d\n-----------------------------------------\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 134192kb
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: 20ms
memory: 134328kb
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: 14ms
memory: 134164kb
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: 181ms
memory: 141212kb
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: -100
Wrong Answer
time: 338ms
memory: 180124kb
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:
wrong answer 1717th numbers differ - expected: '149415', found: '149317'