QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448379 | #8525. Mercenaries | 2745518585 | WA | 28ms | 280676kb | C++20 | 3.9kb | 2024-06-19 15:49:28 | 2024-06-19 15:49:30 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1000001;
int n,m,c[N],e[N],p[N];
struct pt
{
ll x,y;
pt():x(0),y(0) {}
pt(ll x,ll y):x(x),y(y) {}
friend pt operator+(const pt &a,const pt &b)
{
return pt(a.x+b.x,a.y+b.y);
}
friend pt operator-(const pt &a,const pt &b)
{
return pt(a.x-b.x,a.y-b.y);
}
friend ll operator^(const pt &a,const pt &b)
{
return a.x*b.y-a.y*b.x;
}
friend bool operator<(pt a,pt b)
{
return a.x<b.x;
}
}a[N];
struct str
{
ll a,b,w;
ll operator()(const pt &p)
{
return a*p.x+b*p.y;
}
}d[N];
vector<pt> b[N];
vector<pt> solve(const vector<pt> &a)
{
vector<pt> p;
for(auto i:a)
{
while(p.size()>1&&((p[p.size()-2]-p[p.size()-1])^(p[p.size()-1]-i))>0) p.pop_back();
p.push_back(i);
}
return p;
}
vector<pt> merge(const vector<pt> &a,const vector<pt> &b)
{
vector<pt> p;
p.push_back(pt(0,max(a[0].y,b[0].y)));
int x1=0,x2=0;
while(x1+1<a.size()||x2+1<b.size())
{
if(x1+1<a.size()&&(x2+1==b.size()||((a[x1]-a[x1+1])^(b[x2]-b[x2+1]))<=0)) ++x1,p.push_back(p.back()+(a[x1]-a[x1-1]));
else ++x2,p.push_back(p.back()+(b[x2]-b[x2-1]));
}
return p;
}
vector<pt> max(const vector<pt> &a,const vector<pt> &b)
{
vector<pt> p;
p.push_back(pt(0,max(a[0].y,b[0].y)));
int x1=0,x2=0;
while(x1+1<a.size()||x2+1<b.size())
{
if(x1+1<a.size()&&(x2+1==b.size()||a[x1+1].x<=b[x2+1].x))
{
p.push_back(a[++x1]);
if(x2+1<b.size()&&p.back().x==b[x2+1].x) p.back().y=std::max(p.back().y,b[++x2].y);
}
else p.push_back(b[++x2]);
}
return solve(p);
}
bool find(vector<pt> p,int &t,str k)
{
while(t+1<p.size()&&k(p[t])<k(p[t+1])) ++t;
return k(p[t])>=k.w;
}
namespace sgt
{
struct tree
{
int l,r,ts,tw;
vector<pt> s,w;
}T[N<<2];
void pushup(int x)
{
T[x].w=merge(T[x<<1].w,T[x<<1|1].w);
T[x].s=max(merge(T[x<<1].s,T[x<<1|1].w),T[x<<1|1].s);
}
void build(int x,int l,int r)
{
T[x].l=l,T[x].r=r;
if(l==r)
{
T[x].s={pt(0,0),a[l]};
T[x].w={pt(0,0)};
for(auto i:b[l]) T[x].w.push_back(i);
solve(T[x].s),solve(T[x].w);
return;
}
int z=l+r>>1;
build(x<<1,l,z);
build(x<<1|1,z+1,r);
pushup(x);
}
int sum(int x,int r,str k)
{
if(T[x].r<=r&&!find(T[x].s,T[x].ts,k)) return 0;
if(T[x].l==T[x].r) return T[x].l;
int z=T[x].l+T[x].r>>1,s=0;
if(r>z) s=sum(x<<1|1,r,k);
if(s==0)
{
find(T[x<<1|1].w,T[x<<1|1].tw,k);
k.w-=k(T[x<<1|1].w[T[x<<1|1].tw]);
s=sum(x<<1,r,k);
}
return s;
}
}
bool cmp(int x,int y)
{
return d[x].a*d[y].b<d[y].a*d[x].b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
if(i>1)
{
int k;
scanf("%d",&k);
for(int j=1;j<=k;++j)
{
ll x,y;
scanf("%lld%lld",&x,&y);
b[i].push_back(pt(x,y));
}
sort(b[i].begin(),b[i].end());
}
scanf("%lld%lld",&a[i].x,&a[i].y);
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d%lld%lld%lld",&c[i],&d[i].a,&d[i].b,&d[i].w);
}
for(int i=1;i<=m;++i) p[i]=i;
sort(p+1,p+m+1,cmp);
sgt::build(1,1,n);
for(int i=1;i<=m;++i)
{
e[p[i]]=sgt::sum(1,c[p[i]],d[p[i]]);
}
for(int i=1;i<=m;++i)
{
if(e[i]==0) printf("-1\n");
else printf("%d\n",e[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 28ms
memory: 279060kb
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: -100
Wrong Answer
time: 27ms
memory: 280676kb
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:
wrong answer 3rd numbers differ - expected: '-1', found: '1'