QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448447 | #8525. Mercenaries | 2745518585 | WA | 71ms | 537036kb | C++20 | 5.1kb | 2024-06-19 16:58:10 | 2024-06-19 16:58:11 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline char gc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T> inline void read(T &x)
{
T u=1,t=0;char c=gc();
while(c<'0'||c>'9') {if(c=='-') u=-1; c=gc();}
while(c>='0'&&c<='9') t*=10,t+=c-'0',c=gc();
x=u*t;return;
}
template<typename T,typename ...O> inline void read(T &x,O &...o) {read(x),read(o...);}
template<typename T> inline void print(T x)
{
if(x==0) return putchar('0'),void();
if(x<0) putchar('-'),x=-x;
int c[129]={0},k=0;
while(x) c[++k]=x%10,x/=10;
for(int i=k;i;--i) putchar(c[i]+'0');
}
template<typename T,typename ...O> inline void print(T x,O ...o) {print(x),putchar(' '),print(o...);}
const int N=2000001;
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<(const pt &a,const pt &b)
{
if(a.x==b.x) return a.x<b.x;
return a.y<b.y;
}
}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(const 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);
T[x].s=solve(T[x].s);
T[x].w=solve(T[x].w);
// printf("%d %d:\n",l,r);
// for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
// for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
return;
}
int z=l+r>>1;
build(x<<1,l,z);
build(x<<1|1,z+1,r);
pushup(x);
// printf("%d %d:\n",l,r);
// for(auto i:T[x].s) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
// for(auto i:T[x].w) printf("(%lld,%lld) ",i.x,i.y);printf("\n");
}
int sum(int x,int r,str &k)
{
if(T[x].r<=r&&!find(T[x].s,T[x].ts,k))
{
find(T[x].w,T[x].tw,k);
k.w-=k(T[x].w[T[x].tw]);
return 0;
}
if(T[x].l==T[x].r) return T[x].l;
int z=T[x].l+T[x].r>>1;
if(r>z)
{
int p=sum(x<<1|1,r,k);
if(p) return p;
}
return sum(x<<1,r,k);
}
}
bool cmp(int x,int y)
{
if(d[x].a*d[y].b==d[y].a*d[x].b) return d[x].a+d[x].b>d[y].a+d[y].b;
return d[x].a*d[y].b<d[y].a*d[x].b;
}
int main()
{
read(n);
for(int i=1;i<=n;++i)
{
if(i>1)
{
int k;
read(k);
for(int j=1;j<=k;++j)
{
ll x,y;
read(x,y);
b[i].push_back(pt(x,y));
}
sort(b[i].begin(),b[i].end());
}
read(a[i].x,a[i].y);
}
read(m);
for(int i=1;i<=m;++i)
{
read(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: 71ms
memory: 537032kb
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: 55ms
memory: 537036kb
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: 52ms
memory: 536308kb
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:
wrong answer 4th numbers differ - expected: '1', found: '-1'