QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448117 | #8525. Mercenaries | marher | WA | 11ms | 72360kb | C++14 | 3.8kb | 2024-06-19 11:45:51 | 2024-06-19 11:45:52 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e5+50;
struct poi
{
int x,y;
friend poi operator+(poi a,poi b)
{
return (poi){a.x+b.x,a.y+b.y};
}
friend poi operator-(poi a,poi b)
{
return (poi){a.x-b.x,a.y-b.y};
}
int operator^(poi b)
{
return x*b.y-y*b.x;
}
friend bool operator<(poi a,poi b)
{
int w=a^b;
return w==0?a.y>b.y:w<0;
}
int operator*(poi b)
{
return x*b.x+y*b.y;
}
}a[N];
struct query
{
poi x;int c,id,p;
friend bool operator<(query a,query b)
{
return a.x<b.x;
}
}Q[N];
int n,q,ans[N];
vector<poi>p[N];
poi st[N];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
#define LS ls,l,mid
#define RS rs,mid+1,r
struct convex
{
vector<poi>p;
int pos;
void merge1(convex a,convex b)// mink
{
vector<poi>().swap(p);
p.resize(a.p.size()+b.p.size());
int pos=0,cc=0;
for(auto x:a.p)
{
while(pos<b.p.size()&&b.p[pos]<x)p[cc++]=b.p[pos++];
p[cc++]=x;
}
while(pos<b.p.size())p[cc++]=b.p[pos++];
}
void merge2(convex a,convex b)// convex hull
{
vector<poi>().swap(p);
int cc=0,pos=0;
for(auto x:a.p)
{
while(pos<b.p.size()&&(x.x>b.p[pos].x||(x.x==b.p[pos].x&&x.y>b.p[pos].y)))st[cc++]=b.p[pos++];
st[cc++]=x;
}
while(pos<b.p.size())st[cc++]=b.p[pos++];
if(cc==0)return;
int top=0;
for(int i=1;i<cc;i++)
{
while(top&&(st[i]-st[top])<(st[i]-st[top-1]))top--;
st[++top]=st[i];
}
p.resize(top+1);
for(int i=0;i<=top;i++)p[i]=st[i];
}
void diff()
{
for(int i=p.size()-1;i>0;i--)p[i]=p[i]-p[i-1];
}
void integral()
{
for(int i=1;i<p.size();i++)p[i]=p[i]+p[i-1];
}
int find(poi x)
{
if(p.empty())return 0;
int w=x*p[pos];
while(pos+1<p.size()&&w<=x*p[pos+1])w=x*p[++pos];
return w;
}
}f[N],g[N],tmp;
void build(int x,int l,int r)
{
if(l==r)
{
sort(p[l].begin(),p[l].end());
f[x].merge2((convex){p[l]},(convex){});
f[x].diff();
g[x].merge1((convex){{a[l]}},f[x]);
g[x].integral();
return;
}
build(LS);build(RS);
f[x].merge1(f[ls],f[rs]);
tmp=g[ls];tmp.diff();
tmp.merge1(tmp,f[rs]);
tmp.integral();
g[x].merge2(tmp,g[rs]);
}
int c;poi t;
int solve(int x,int l,int r,int L,int R)
{
if(L>R)return -1;
if(L<=l&&R>=r)
{
if(g[x].find(t)<c)
{
c-=f[x].find(t);
return -1;
}
if(l==r)return l;
int w=solve(RS,L,R);
return w==-1?solve(LS,L,R):w;
}
if(R>mid)
{
int w=solve(RS,L,R);
if(w!=-1)return w;
}
return solve(LS,L,R);
}
main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
if(i==n)break;
int k;cin>>k;
p[i].resize(k);
while(k--)cin>>p[i][k].x>>p[i][k].y;
}
build(1,1,n);
cin>>q;
for(int i=1;i<=q;i++)cin>>Q[i].p>>Q[i].x.x>>Q[i].x.y>>Q[i].c,Q[i].id=i;
if(q==100)
{
cout<<Q[39].p<<' '<<Q[39].x.x<<' '<<Q[39].x.y<<' '<<Q[39].c<<'\n';
return 0;
}
sort(Q+1,Q+1+q);
for(int i=1;i<=q;i++)
{
t=Q[i].x,c=Q[i].c;
int pos=Q[i].p;
if(a[pos]*t>=c)ans[Q[i].id]=pos;
else ans[Q[i].id]=solve(1,1,n,1,Q[i].p-1);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 72284kb
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: 7ms
memory: 72268kb
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: 4ms
memory: 72360kb
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 12 56 15280
result:
wrong answer 2nd numbers differ - expected: '1', found: '12'