QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#455227#8525. Mercenarieskkkgjyismine4WA 4ms16036kbC++233.7kb2024-06-25 21:16:022024-06-25 21:16:02

Judging History

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

  • [2024-06-25 21:16:02]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:16036kb
  • [2024-06-25 21:16:02]
  • 提交

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'