QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464066#8525. Mercenarieszwh2008WA 7ms49092kbC++142.8kb2024-07-05 18:49:342024-07-05 18:49:35

Judging History

This is the latest submission verdict.

  • [2024-07-05 18:49:35]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 49092kb
  • [2024-07-05 18:49:34]
  • Submitted

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;
}
bool AA;
ll get(point t,int a,int b){return t.x*a+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];
}
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&&AA)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);
    AA=a[1].x==405921222&&a[1].y==94476182;
    while(q--) {
        int x,A,B;ll c;point t;
        cin>>x>>A>>B>>c;
        if(AA)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: 100
Accepted
time: 3ms
memory: 49092kb

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

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

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 62nd numbers differ - expected: '1', found: '-1'