QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#455235#8525. Mercenarieskkkgjyismine4RE 0ms0kbC++233.8kb2024-06-25 21:40:342024-06-25 21:40:34

Judging History

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

  • [2024-06-25 21:40:34]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: