QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#455235 | #8525. Mercenaries | kkkgjyismine4 | RE | 0ms | 0kb | C++23 | 3.8kb | 2024-06-25 21:40:34 | 2024-06-25 21:40:34 |
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){
if(!g.size()){res=f;return;}
if(!f.size()){res=g;return;}
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(b[n2],a[n1]))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;
c[0].x=-1;
for(int i=1;i<=tot;++i){
if(c[i-1].x==c[i].x)continue;
while(tail>1&&cmp(stk[tail]-stk[tail-1],c[i]-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)){
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){
assert(s[p]*ra+m[p]*rb>=rc);
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);
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: 0
Runtime Error
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