QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446698 | #8525. Mercenaries | 275307894a | WA | 12ms | 49068kb | C++14 | 3.3kb | 2024-06-17 15:17:56 | 2024-06-17 15:17:56 |
Judging History
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'