QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448117#8525. MercenariesmarherWA 11ms72360kbC++143.8kb2024-06-19 11:45:512024-06-19 11:45:52

Judging History

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

  • [2024-06-19 11:45:52]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:72360kb
  • [2024-06-19 11:45:51]
  • 提交

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.y>b.y: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])<(st[i]-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){});
        f[x].diff();
        g[x].merge1((convex){{a[l]}},f[x]);
        g[x].integral();
        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);
}

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);
    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;
    if(q==100)
    {
        cout<<Q[39].p<<' '<<Q[39].x.x<<' '<<Q[39].x.y<<' '<<Q[39].c<<'\n';
        return 0;
    }
    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: 11ms
memory: 72284kb

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

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

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 12 56 15280

result:

wrong answer 2nd numbers differ - expected: '1', found: '12'