QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448175#8525. MercenariesmarherWA 421ms105216kbC++143.8kb2024-06-19 13:15:572024-06-19 13:15:57

Judging History

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

  • [2024-06-19 13:15:57]
  • 评测
  • 测评结果:WA
  • 用时:421ms
  • 内存:105216kb
  • [2024-06-19 13:15:57]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e5+50;

struct poi
{
    int x,y;

    friend poi operator+(poi a,poi b)
    {
        return (poi){a.x+b.x,a.y+b.y};
    }

    friend poi operator-(poi a,poi b)
    {
        return (poi){a.x-b.x,a.y-b.y};
    }

    int operator^(poi b)
    {
        return x*b.y-y*b.x;
    }

    friend bool operator<(poi a,poi b)
    {
        int w=a^b;
        return w==0?a.x>b.x:w<0;
    }
    
    int operator*(poi b)
    {
        return x*b.x+y*b.y;
    }
}a[N];

struct query
{
    poi x;int c,id,p;
    
    friend bool operator<(query a,query b)
    {
        return a.x<b.x;
    }
}Q[N];

int n,q,ans[N];
vector<poi>p[N];
poi st[N];

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
#define LS ls,l,mid
#define RS rs,mid+1,r

struct convex
{
    vector<poi>p;
    int pos;

    void merge1(convex a,convex b)// mink
    {
        vector<poi>().swap(p);
        p.resize(a.p.size()+b.p.size());
        int pos=0,cc=0;
        for(auto x:a.p)
        {
            while(pos<b.p.size()&&b.p[pos]<x)p[cc++]=b.p[pos++];
            p[cc++]=x;
        }
        while(pos<b.p.size())p[cc++]=b.p[pos++];
    }
    
    void merge2(convex a,convex b)// convex hull
    {
        vector<poi>().swap(p);
        int cc=0,pos=0;
        for(auto x:a.p)
        {
            while(pos<b.p.size()&&(x.x>b.p[pos].x||(x.x==b.p[pos].x&&x.y>b.p[pos].y)))st[cc++]=b.p[pos++];
            st[cc++]=x;
        }
        while(pos<b.p.size())st[cc++]=b.p[pos++];
        if(cc==0)return;
        int top=0;
        for(int i=1;i<cc;i++)
        {
            while(top&&(st[i]-st[top-1])<(st[top]-st[top-1]))top--;
            st[++top]=st[i];
        }
        p.resize(top+1);
        for(int i=0;i<=top;i++)p[i]=st[i];
    }

    void diff()
    {
        for(int i=p.size()-1;i>0;i--)p[i]=p[i]-p[i-1];
    }
    
    void integral()
    {
        for(int i=1;i<p.size();i++)p[i]=p[i]+p[i-1];
    }

    int find(poi x)
    {
        if(p.empty())return 0;
        int w=x*p[pos];
        while(pos+1<p.size()&&w<=x*p[pos+1])w=x*p[++pos];
        return w;
    }
}f[N],g[N],tmp;

void build(int x,int l,int r)
{
    if(l==r)
    {
        sort(p[l].begin(),p[l].end());
        f[x].merge2((convex){p[l]},(convex){});
        g[x]=f[x];
        for(auto&t:g[x].p)t=t+a[l];
        f[x].diff();
        return;
    }
    build(LS);build(RS);
    f[x].merge1(f[ls],f[rs]);
    tmp=g[ls];tmp.diff();
    tmp.merge1(tmp,f[rs]);
    tmp.integral();
    g[x].merge2(tmp,g[rs]);
}

int c;poi t;

int solve(int x,int l,int r,int L,int R)
{
    if(L>R)return -1;
    if(L<=l&&R>=r)
    {
        if(g[x].find(t)<c)
        {
            c-=f[x].find(t);
            return -1;
        }
        if(l==r)return l;
        int w=solve(RS,L,R);
        return w==-1?solve(LS,L,R):w;
    }
    if(R>mid)
    {
        int w=solve(RS,L,R);
        if(w!=-1)return w;
    }
    return solve(LS,L,R);
}

void dfs(int x,int l,int r)
{
    f[x].integral();
    if(l==r)return;
    dfs(LS);dfs(RS);
}

main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        if(i==n)break;
        int k;cin>>k;
        p[i].resize(k);
        while(k--)cin>>p[i][k].x>>p[i][k].y;
    }
    build(1,1,n);dfs(1,1,n);
    cin>>q;
    for(int i=1;i<=q;i++)cin>>Q[i].p>>Q[i].x.x>>Q[i].x.y>>Q[i].c,Q[i].id=i;
    sort(Q+1,Q+1+q);
    for(int i=1;i<=q;i++)
    {
        t=Q[i].x,c=Q[i].c;
        int pos=Q[i].p;
        if(a[pos]*t>=c)ans[Q[i].id]=pos;
        else ans[Q[i].id]=solve(1,1,n,1,Q[i].p-1);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 79992kb

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: 8ms
memory: 80540kb

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: 7ms
memory: 78964kb

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: -100
Wrong Answer
time: 421ms
memory: 105216kb

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:

wrong answer 313th numbers differ - expected: '1', found: '-1'