QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446698#8525. Mercenaries275307894aWA 12ms49068kbC++143.3kb2024-06-17 15:17:562024-06-17 15:17:56

Judging History

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

  • [2024-06-17 15:17:56]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:49068kb
  • [2024-06-17 15:17:56]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
using cp=complex<ll>;
cp A[N];
using node=vector<cp>;
node B[N];
int n,q;
ll cross(cp x,cp y){return x.real()*y.imag()-x.imag()*y.real();}
bool cmp(cp x,cp y){return cross(x,y)<=0;}
bool ord(cp x,cp y){return make_pair(x.real(),x.imag())<make_pair(y.real(),y.imag());}
node convex_hull(const node &A){
	int len=A.size();
	static cp st[N*6];int sh=-1;
	for(auto i:A){
		while(sh>=0&&i.imag()>=st[sh].imag()) sh--;
		while(sh>=1&&cross(st[sh]-st[sh-1],i-st[sh])>=0) sh--;
		st[++sh]=i; 
	}
	vector<cp> B(st,st+sh+1);
	return B;
}
node minkowski(node A,node B){
	int lA=A.size(),lB=B.size();
	adjacent_difference(all(A),A.begin());
	adjacent_difference(all(B),B.begin());
	node C(lA+lB-1);
	C[0]=A[0]+B[0];
	merge(A.begin()+1,A.end(),B.begin()+1,B.end(),C.begin()+1,cmp);
	partial_sum(C.begin(),C.end(),C.begin());
	return C;
}
node merge(const node &A,const node &B){
	node C(A.size()+B.size());
	merge(all(A),all(B),C.begin(),ord);
	return C;
}
ll calc(const node &A,cp z){
	int l=0,r=A.size(),mid;
	while(l+1<r) mid=l+r>>1,(cmp(A[mid]-A[mid-1],z)?l:r)=mid;
	return cross(z,A[mid]);
}
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	node f[M],g[M];
	void build(int l=1,int r=n,int v=1){
		if(l==r){
			f[v].push_back(A[l]);
			sort(all(B[l-1]),ord);
			g[v]=convex_hull(B[l-1]);
			return;
		}
		int m=l+r>>1;
		build(l,m,ls);build(m+1,r,rs);
		g[v]=minkowski(g[ls],g[rs]);
		f[v]=convex_hull(merge(f[rs],minkowski(f[ls],g[rs])));
	}
	int qry(int x,int y,cp z,ll &w,int l=1,int r=n,int v=1){
		if(x<=l&&r<=y&&calc(f[v],z)<w){
			w-=calc(g[v],z);
			return -1;
		}
		if(l==r) return l;int m=l+r>>1;
		int p=(y>m?qry(x,y,z,w,m+1,r,rs):-1);
		return ~p?p:(x<=m?qry(x,y,z,w,l,m,ls):-1);
	}
}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<=n;i++){
		int x,y;scanf("%d%d",&x,&y);
		A[i]=cp(x,y);
		if(i==n) break;
		int k;scanf("%d",&k);
		B[i].resize(k);
		for(int j=0;j<k;j++){
			int x,y;scanf("%d%d",&x,&y);
			B[i][j]=cp(x,y);
		}
	}
	for(i=1;i<=n;i++) B[i-1].push_back(cp(0,0));
	Tree::build();
	scanf("%d",&q);
	while(q--){
		int v,x,y;cp z;ll w;
		scanf("%d%d%d%lld",&v,&x,&y,&w);
		printf("%d\n",Tree::qry(1,v,cp(y,-x),w));
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 49068kb

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:

wrong answer 7th numbers differ - expected: '1', found: '-1'