QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448447#8525. Mercenaries2745518585WA 71ms537036kbC++205.1kb2024-06-19 16:58:102024-06-19 16:58:11

Judging History

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

  • [2024-06-19 16:58:11]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:537036kb
  • [2024-06-19 16:58:10]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline char gc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T> inline void read(T &x)
{
    T u=1,t=0;char c=gc();
    while(c<'0'||c>'9') {if(c=='-') u=-1; c=gc();}
    while(c>='0'&&c<='9') t*=10,t+=c-'0',c=gc();
    x=u*t;return;
}
template<typename T,typename ...O> inline void read(T &x,O &...o) {read(x),read(o...);}
template<typename T> inline void print(T x)
{
    if(x==0) return putchar('0'),void();
    if(x<0) putchar('-'),x=-x;
    int c[129]={0},k=0;
    while(x) c[++k]=x%10,x/=10;
    for(int i=k;i;--i) putchar(c[i]+'0');
}
template<typename T,typename ...O> inline void print(T x,O ...o) {print(x),putchar(' '),print(o...);}
const int N=2000001;
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<(const pt &a,const pt &b)
    {
        if(a.x==b.x) return a.x<b.x;
        return a.y<b.y;
    }
}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(const 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);
            T[x].s=solve(T[x].s);
            T[x].w=solve(T[x].w);
            // printf("%d %d:\n",l,r);
            // for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
            // for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
            return;
        }
        int z=l+r>>1;
        build(x<<1,l,z);
        build(x<<1|1,z+1,r);
        pushup(x);
        // printf("%d %d:\n",l,r);
        // for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
        // for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
    }
    int sum(int x,int r,str &k)
    {
        if(T[x].r<=r&&!find(T[x].s,T[x].ts,k))
        {
            find(T[x].w,T[x].tw,k);
            k.w-=k(T[x].w[T[x].tw]);
            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;
        }
        return sum(x<<1,r,k);
    }
}
bool cmp(int x,int y)
{
    if(d[x].a*d[y].b==d[y].a*d[x].b) return d[x].a+d[x].b>d[y].a+d[y].b;
    return d[x].a*d[y].b<d[y].a*d[x].b;
}
int main()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        if(i>1)
        {
            int k;
            read(k);
            for(int j=1;j<=k;++j)
            {
                ll x,y;
                read(x,y);
                b[i].push_back(pt(x,y));
            }
            sort(b[i].begin(),b[i].end());
        }
        read(a[i].x,a[i].y);
    }
    read(m);
    for(int i=1;i<=m;++i)
    {
        read(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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 71ms
memory: 537032kb

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

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

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:

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