QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461627 | #8525. Mercenaries | charchach | WA | 31ms | 247164kb | C++14 | 5.3kb | 2024-07-02 20:54:12 | 2024-07-02 20:54:16 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#define LL long long
#include<vector>
using namespace std;
const int N = 1e6 + 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], D[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;i >= 1;-- i)
C[i] = A[i + 1] - A[i];
for (int i = n2;i >= 1;-- i)
D[i] = B[i + 1] - B[i];
for (int i = 1;i <= n1;++ i)
A[i] = C[i];
for (int i = 1;i <= n2;++ i)
B[i] = D[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)
{
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 > 2)
{
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;
}
};
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]), road[l]};
else
bd(l, mid, ls), bd(mid + 1, r, rs), tr[p] = tr[ls] + tr[rs];
}
int ans;
void Ask(LL x, LL y, LL c, int p)
{
int l = tr[p].l, r = tr[p].r;
if (r < ans || tr[p].a.ask(x, y) < c)
return;
if (l == r)
{
ans = 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;
if (l >= sl && r <= sr)
{
Ask(x, y, c, p);
return tr[p].b.ask(x, y);
}
LL res = 0;
if (sr > mid)
res = ask(sl, sr, x, y, c, rs);
if (sl <= mid && ans != -1)
{
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);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 31ms
memory: 247164kb
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 -1 3 3 2 2 1 -1 1 -1 -1 -1
result:
wrong answer 1st numbers differ - expected: '1', found: '-1'