QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448390#8525. Mercenaries2745518585WA 48ms276384kbC++203.9kb2024-06-19 15:55:282024-06-19 15:55:29

Judging History

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

  • [2024-06-19 15:55:29]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:276384kb
  • [2024-06-19 15:55:28]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1000001;
int n,m,c[N],e[N],p[N];
struct pt
{
    ll x,y;
    pt():x(0),y(0) {}
    pt(ll x,ll y):x(x),y(y) {}
    friend pt operator+(const pt &a,const pt &b)
    {
        return pt(a.x+b.x,a.y+b.y);
    }
    friend pt operator-(const pt &a,const pt &b)
    {
        return pt(a.x-b.x,a.y-b.y);
    }
    friend ll operator^(const pt &a,const pt &b)
    {
        return a.x*b.y-a.y*b.x;
    }
    friend bool operator<(pt a,pt b)
    {
        return a.x<b.x;
    }
}a[N];
struct str
{
    ll a,b,w;
    ll operator()(const pt &p)
    {
        return a*p.x+b*p.y;
    }
}d[N];
vector<pt> b[N];
vector<pt> solve(const vector<pt> &a)
{
    vector<pt> p;
    for(auto i:a)
    {
        while(p.size()>1&&((p[p.size()-2]-p[p.size()-1])^(p[p.size()-1]-i))>0) p.pop_back();
        p.push_back(i);
    }
    return p;
}
vector<pt> merge(const vector<pt> &a,const vector<pt> &b)
{
    vector<pt> p;
    p.push_back(pt(0,max(a[0].y,b[0].y)));
    int x1=0,x2=0;
    while(x1+1<a.size()||x2+1<b.size())
    {
        if(x1+1<a.size()&&(x2+1==b.size()||((a[x1]-a[x1+1])^(b[x2]-b[x2+1]))<=0)) ++x1,p.push_back(p.back()+(a[x1]-a[x1-1]));
        else ++x2,p.push_back(p.back()+(b[x2]-b[x2-1]));
    }
    return p;
}
vector<pt> max(const vector<pt> &a,const vector<pt> &b)
{
    vector<pt> p;
    p.push_back(pt(0,max(a[0].y,b[0].y)));
    int x1=0,x2=0;
    while(x1+1<a.size()||x2+1<b.size())
    {
        if(x1+1<a.size()&&(x2+1==b.size()||a[x1+1].x<=b[x2+1].x))
        {
            p.push_back(a[++x1]);
            if(x2+1<b.size()&&p.back().x==b[x2+1].x) p.back().y=std::max(p.back().y,b[++x2].y);
        }
        else p.push_back(b[++x2]);
    }
    return solve(p);
}
bool find(vector<pt> p,int &t,str k)
{
    while(t+1<p.size()&&k(p[t])<=k(p[t+1])) ++t;
    return k(p[t])>=k.w;
}
namespace sgt
{
    struct tree
    {
        int l,r,ts,tw;
        vector<pt> s,w;
    }T[N<<2];
    void pushup(int x)
    {
        T[x].w=merge(T[x<<1].w,T[x<<1|1].w);
        T[x].s=max(merge(T[x<<1].s,T[x<<1|1].w),T[x<<1|1].s);
    }
    void build(int x,int l,int r)
    {
        T[x].l=l,T[x].r=r;
        if(l==r)
        {
            T[x].s={pt(0,0),a[l]};
            T[x].w={pt(0,0)};
            for(auto i:b[l]) T[x].w.push_back(i);
            solve(T[x].s),solve(T[x].w);
            return;
        }
        int z=l+r>>1;
        build(x<<1,l,z);
        build(x<<1|1,z+1,r);
        pushup(x);
    }
    int sum(int x,int r,str k)
    {
        if(T[x].r<=r&&!find(T[x].s,T[x].ts,k)) return 0;
        if(T[x].l==T[x].r) return T[x].l;
        int z=T[x].l+T[x].r>>1;
        if(r>z)
        {
            int p=sum(x<<1|1,r,k);
            if(p) return p;
            find(T[x<<1|1].w,T[x<<1|1].tw,k);
            k.w-=k(T[x<<1|1].w[T[x<<1|1].tw]);
        }
        return sum(x<<1,r,k);
    }
}
bool cmp(int x,int y)
{
    return d[x].a*d[y].b<d[y].a*d[x].b;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        if(i>1)
        {
            int k;
            scanf("%d",&k);
            for(int j=1;j<=k;++j)
            {
                ll x,y;
                scanf("%lld%lld",&x,&y);
                b[i].push_back(pt(x,y));
            }
            sort(b[i].begin(),b[i].end());
        }
        scanf("%lld%lld",&a[i].x,&a[i].y);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%lld%lld%lld",&c[i],&d[i].a,&d[i].b,&d[i].w);
    }
    for(int i=1;i<=m;++i) p[i]=i;
    sort(p+1,p+m+1,cmp);
    sgt::build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        e[p[i]]=sgt::sum(1,c[p[i]],d[p[i]]);
    }
    for(int i=1;i<=m;++i)
    {
        if(e[i]==0) printf("-1\n");
        else printf("%d\n",e[i]);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 40ms
memory: 276384kb

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

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

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
1
2
-1
3
2
1
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
1
-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
1
-1
-1
1
1
1
1
2
1
-1
-1
-1
1
2
1
1
-1
-1
1
3
2
2

result:

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