QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#455227 | #8525. Mercenaries | kkkgjyismine4 | WA | 4ms | 16036kb | C++23 | 3.7kb | 2024-06-25 21:16:02 | 2024-06-25 21:16:02 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define i28 __int128
#define pii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define db double
using namespace std;
int n,q,tt1,tt2,tot,tail;
ll s[200050],m[200050];
struct Complex{ll x,y;}a[1400050],b[1400500],c[1400005],stk[1400005];
bool operator<(Complex a,Complex b){if(a.x==b.x)return a.y>b.y;return a.x<b.x; }
vector<Complex>f[800005],g[800005];
#define vc vector<Complex>
vc vec[200050];
Complex operator+(Complex a,Complex b){a.x+=b.x,a.y+=b.y;return a;}
Complex operator-(Complex a,Complex b){a.x-=b.x,a.y-=b.y;return a;}
bool cmp(Complex a,Complex b){
if(a.x==0)return (a.y<0);
ll dx=a.x,dy=a.y,dx1=b.x,dy1=b.y;
if(dx<0)dy=-dy,dx=-dx;
if(dx1<0)dy1=-dy1,dx1=-dx1;
return dy*dx1<dy1*dx;
}
void Merge(vc &res,vc &f,vc &g){
tt1=tt2=0;for(auto v:f)a[++tt1]=v;for(auto v:g)b[++tt2]=v;
for(int i=tt1;i>=2;--i)a[i]=a[i]-a[i-1];
for(int i=tt2;i>=2;--i)b[i]=b[i]-b[i-1];
res.clear(),res.pb(Complex{a[1]+b[1]});
int n1=2,n2=2;
while(n1<=tt1&&n2<=tt2){
if(cmp(a[n1],b[n2]))res.pb(a[n1++]);
else res.pb(b[n2++]);
}
while(n1<=tt1)res.pb(a[n1++]);while(n2<=tt2)res.pb(b[n2++]);
for(int i=1;i<res.size();++i)res[i]=res[i]+res[i-1];
}
void merge(vc &res,vc &f,vc &g){
tot=0;int n1=0,n2=0;
while(n1<f.size()&&n2<g.size()){
if(f[n1]<g[n2])c[++tot]=f[n1++];
else c[++tot]=g[n2++];
}
while(n1<f.size())c[++tot]=f[n1++];while(n2<g.size())c[++tot]=g[n2++];tail=0;ll mx=-1;
for(int i=1;i<=tot;++i){
if(mx>=c[i].y)continue;mx=c[i].y;
while(tail>1&&cmp(stk[tail]-stk[tail-1],c[tail]-stk[tail]))--tail;
stk[++tail]=c[i];
}res.clear();
for(int i=1;i<=tail;++i)res.pb(stk[i]);
}
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
void bd(int p,int l,int r){
if(l==r){
vc Be;
sort(vec[l].begin(),vec[l].end());
merge(g[p],vec[l],Be);
f[p].pb(Complex{s[l],m[l]});
if(l<n)Merge(f[p],f[p],g[p]);
return;
}
bd(ls,l,mid),bd(rs,mid+1,r);
Merge(f[p],f[ls],f[rs]);
Merge(g[p],g[ls],f[rs]);
merge(g[p],g[p],g[rs]);
}
ll ra,rb,rc;
bool chk(int p,ll a,ll b,ll c){
int ql=1,qr=f[p].size()-1,ans=0;
while(ql<=qr){
int Mid=ql+qr>>1;
if(cmp(Complex{b,-a},f[p][Mid]-f[p][Mid-1]))ans=Mid,ql=Mid+1;
else qr=Mid-1;
}
return (a*f[p][ans].x+b*f[p][ans].y>=c);
}
int getpos(int p,int l,int r){
if(!chk(p,ra,rb,rc)){
if(l==r&&l==n)return 0;
int ql=1,qr=g[p].size()-1,ans=0;
while(ql<=qr){
int Mid=ql+qr>>1;
if(cmp(Complex{rb,-ra},g[p][Mid]-g[p][Mid-1]))ans=Mid,ql=Mid+1;
else qr=Mid-1;
}
if(rc>=ra*g[p][ans].x+rb*g[p][ans].y)rc-=ra*g[p][ans].x+rb*g[p][ans].y;
else rc=0;
return 0;
}
if(l==r)return l;
int res=getpos(rs,mid+1,r);
if(res)return res;
return getpos(ls,l,mid);
}
int qry(int p,int l,int r,int pos){
if(pos>=r){
if(chk(p,ra,rb,rc))return getpos(p,l,r);
if(l==r&&l==n)return 0;
int ql=1,qr=g[p].size()-1,ans=0;
while(ql<=qr){
int Mid=ql+qr>>1;
if(cmp(Complex{rb,-ra},g[p][Mid]-g[p][Mid-1]))ans=Mid,ql=Mid+1;
else qr=Mid-1;
}
if(rc>=ra*g[p][ans].x+rb*g[p][ans].y)rc-=ra*g[p][ans].x+rb*g[p][ans].y;
else rc=0;
return 0;
}
int res=0;
if(pos>mid)res=qry(rs,mid+1,r,pos);
if(res)return res;
return qry(ls,l,mid,pos);
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
scanf("%lld%lld",&s[i],&m[i]);
ll a,b;if(i==n)break;
int sz;scanf("%d",&sz);while(sz--)scanf("%lld%lld",&a,&b),vec[i].pb(Complex{a,b});
}bd(1,1,n);cin>>q;
while(q--){
int p,v;ll a,b,c;
scanf("%d%lld%lld%lld",&p,&a,&b,&c),ra=a,rb=b,rc=c;
if(s[p]*a+m[p]*b>=c){printf("%d\n",p);continue;}
if(p==1){puts("-1");continue;}
v=qry(1,1,n,p-1);if(!v)v=-1;
printf("%d\n",v);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 14104kb
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: 4ms
memory: 16036kb
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: 0ms
memory: 14164kb
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'