QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448179 | #8525. Mercenaries | marher | WA | 712ms | 266312kb | C++14 | 3.8kb | 2024-06-19 13:23:41 | 2024-06-19 13:23:42 |
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.x>b.x: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-1])^(st[top]-st[top-1]))<=0)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){});
g[x]=f[x];
for(auto&t:g[x].p)t=t+a[l];
f[x].diff();
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);
}
void dfs(int x,int l,int r)
{
f[x].integral();
if(l==r)return;
dfs(LS);dfs(RS);
}
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);dfs(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;
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';
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 78132kb
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: 15ms
memory: 79180kb
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: 0
Accepted
time: 12ms
memory: 80256kb
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:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 422ms
memory: 105460kb
input:
2 309248041 338995438 500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...
output:
2 1 -1 2 2 2 1 1 2 -1 2 2 1 1 2 1 2 2 1 2 2 1 -1 -1 1 -1 2 -1 1 2 1 1 1 1 -1 1 -1 -1 -1 1 2 2 1 1 1 2 -1 -1 1 -1 1 2 -1 1 2 1 2 2 -1 2 1 2 2 -1 2 2 -1 2 1 2 1 -1 -1 1 1 -1 2 1 2 2 1 1 1 1 2 2 -1 -1 1 2 2 -1 2 -1 -1 -1 1 2 1 1 2 2 1 -1 -1 2 2 2 1 -1 1 2 2 -1 1 -1 -1 -1 1 2 1 2 1 -1 -1 1 2 2 -1 2 2 2 ...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 712ms
memory: 266312kb
input:
200000 999999511 993051669 2 5000 5000 5000 5000 1000000000 1000000000 3 5000 5000 5000 5000 5000 5000 995868520 999999999 2 5000 5000 5000 5000 660478427 999992996 3 5000 5000 5000 5000 5000 5000 999999979 999999998 2 5000 5000 5000 5000 861450412 989532141 3 5000 5000 5000 5000 5000 5000 949861679...
output:
145800 198491 112658 29436 38091 122582 7727 87686 192036 97288 60184 836 39235 158331 121422 117149 189664 153018 181334 56603 69911 173097 165342 124250 103223 110099 177817 11459 37052 28918 57236 143793 19234 10313 75590 6597 18202 176357 102394 179685 5171 162359 72023 56758 88764 17257 100583 ...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 80412kb
input:
20 1538 3628 4 2423 3790 3127 3961 2614 3582 2016 4789 1441 276 3 2518 253 4221 265 3236 2574 1668 3370 4 4489 3533 4501 2177 1067 2337 2765 1480 1179 1926 3 4922 2537 1477 653 325 444 3964 2924 2 3415 4463 822 3257 210 4068 2 1969 167 1978 3712 2067 540 4 1560 2211 4050 4196 442 2279 442 2448 2962 ...
output:
5 14 5 1 2 3 6 -1 8 7 2 11 1 8 8 3 3 13 4 5
result:
ok 20 numbers
Test #7:
score: -100
Wrong Answer
time: 8ms
memory: 78388kb
input:
66 121 3727 2 1379 2036 975 1594 205 708 2 523 2978 176 2924 2528 440 4 3182 2078 1340 2166 1563 447 1076 157 3242 2859 5 2029 4660 2789 1593 4534 4137 921 3966 3440 1964 1503 3975 3 1354 3815 825 4981 1710 2692 858 2524 3 3395 3523 2184 4115 4043 3518 2610 731 3 3735 2799 442 1348 3101 2847 4306 14...
output:
9 9 20 -1 3 17 23 2 4 48 13 -1 -1 38 -1 17 -1 -1 -1 51 4 9 -1 -1 3 24 14 5 -1 -1 33 -1 42 5 -1 25 -1 23 24 33 -1 -1 9 -1 -1 1 -1 -1 33 37 5 -1 20 -1 1 25 17 33 -1 32 -1 37 -1 5 42 2
result:
wrong answer 2nd numbers differ - expected: '12', found: '9'