QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463961#8525. Mercenarieszwh2008WA 4ms48916kbC++142.8kb2024-07-05 16:46:362024-07-05 16:46:37

Judging History

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

  • [2024-07-05 16:46:37]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:48916kb
  • [2024-07-05 16:46:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using li=__int128;
const int N=2e5+5;
int n,q;
struct point{
    ll x,y;
    point(){x=y=0;}
    point(ll a,ll b){x=a,y=b;}
    point operator+(const point&t){return point(x+t.x,y+t.y);}
    point operator-(const point&t){return point(x-t.x,y-t.y);}
    ll operator^(const point&t){return x*t.y-y*t.x;}
    bool operator<(const point&t){return x==t.x?y<t.y:x<t.x;}
    friend ostream&operator<<(ostream&o,const point&t){return o<<'('<<t.x<<','<<t.y<<')';}
}a[N];
using conv=vector<point>;
conv v[N];
conv make(conv a) {
    conv b;sort(a.begin(),a.end());
    for(auto i:a) {
        while(b.size()>1&&(i-b.back()^b[b.size()-2]-b.back())>=0)b.pop_back();
        b.push_back(i);
    }return b;
}
conv operator+(conv x,conv y){return x.insert(x.end(),y.begin(),y.end()),make(x);}
conv operator*(conv x,conv y) {
    if(!x.size()||!y.size())return x.size()?x:y;
    conv z={x[0]+y[0]};
    int i=1,j=1;point now=z[0];
    while(i<x.size()||j<y.size()) {
        if(i<x.size()&&(j==y.size()||(x[i]-x[i-1]^y[j]-y[j-1])<=0))now=now+x[i]-x[i-1],i++;
        else now=now+y[j]-y[j-1],j++;z.push_back(now);
    }return z;
}
li get(point t,int a,int b){return (li)t.x*a+(li)t.y*b;}
point calc(conv&w,int a,int b) {
    int l=0,r=(int)w.size()-2,res=r+1,mid;
    while(l<=r)mid=l+r>>1,get(w[mid],a,b)>get(w[mid+1],a,b)?r=mid-1,res=mid:l=mid+1;
    return w[res];
}
bool A;
struct sgt{
    conv f[N<<2],g[N<<2];
    void build(int p,int l,int r) {
        if(l==r)return f[p]=v[l]*conv{a[l]},g[p]=v[l],v[l].clear(),void();
        int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
        g[p]=g[p<<1]*g[p<<1|1],f[p]=f[p<<1]*g[p<<1|1]+f[p<<1|1];
    }
    int qry(int p,int x,int a,int b,ll c,point&t,int l=1,int r=n) {
        if(l>x)return -1;
        if(r<=x) {
            point v=calc(f[p],a,b);
            if(l==r&&l==5806&&A)cout<<v+t<<'\n';
            if(get(v+t,a,b)<c)return t=t+calc(g[p],a,b),-1;
        }
        if(l==r)return l;
        int mid=l+r>>1,res=qry(p<<1|1,x,a,b,c,t,mid+1,r);
        return ~res?res:qry(p<<1,x,a,b,c,t,l,mid);
    }
}T;
int main() {
    #ifndef ONLINE_JUDGE
        freopen(".in","r",stdin);
        freopen(".out","w",stdout);
    #endif
    cin>>n;
    for(int i=1,k;i<n;i++) {
        cin>>a[i].x>>a[i].y>>k,v[i].resize(k);
        for(auto&j:v[i])cin>>j.x>>j.y;
        v[i]=make(v[i]);
    }
    cin>>a[n].x>>a[n].y>>q;
    T.build(1,1,n);
    A=a[1].x==405921222&&a[1].y==94476182;
    while(q--) {
        int x,A,B;ll c;point t;
        cin>>x>>A>>B>>c;
        if(A)cout<<x<<' '<<A<<' '<<B<<' '<<c<<' '<<a[5806]<<' '<<a[5805]<<'\n';
        if(get(a[x],A,B)>=c)cout<<x<<'\n';
        else cout<<T.qry(1,x-1,A,B,c,t)<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 48916kb

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 1 1 1 (0,0) (0,0)
1
2 1 1 1 (0,0) (0,0)
2
3 1 1 1 (0,0) (0,0)
3
3 1 1 9 (0,0) (0,0)
3
3 2 2 20 (0,0) (0,0)
2
3 1 2 18 (0,0) (0,0)
2
3 1 2 19 (0,0) (0,0)
1
3 1 2 20 (0,0) (0,0)
-1
1
2 1 0 4 (0,0) (0,0)
-1
2 1 0 3 (0,0) (0,0)
2
2 1 0 2 (0,0) (0,0)
2

result:

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