QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448393#8525. Mercenaries2745518585TL 39ms269664kbC++204.6kb2024-06-19 16:03:502024-06-19 16:03:51

Judging History

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

  • [2024-06-19 16:03:51]
  • 评测
  • 测评结果:TL
  • 用时:39ms
  • 内存:269664kb
  • [2024-06-19 16:03:50]
  • 提交

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=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);
            T[x].s=solve(T[x].s);
            T[x].w=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()
{
    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: 32ms
memory: 269664kb

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

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

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
Time Limit Exceeded

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:


result: