QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461627#8525. MercenariescharchachWA 31ms247164kbC++145.3kb2024-07-02 20:54:122024-07-02 20:54:16

Judging History

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

  • [2024-07-02 20:54:16]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:247164kb
  • [2024-07-02 20:54:12]
  • 提交

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'