QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463961 | #8525. Mercenaries | zwh2008 | WA | 4ms | 48916kb | C++14 | 2.8kb | 2024-07-05 16:46:36 | 2024-07-05 16:46:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using li=__int128;
const int N=2e5+5;
int n,q;
struct point{
ll x,y;
point(){x=y=0;}
point(ll a,ll b){x=a,y=b;}
point operator+(const point&t){return point(x+t.x,y+t.y);}
point operator-(const point&t){return point(x-t.x,y-t.y);}
ll operator^(const point&t){return x*t.y-y*t.x;}
bool operator<(const point&t){return x==t.x?y<t.y:x<t.x;}
friend ostream&operator<<(ostream&o,const point&t){return o<<'('<<t.x<<','<<t.y<<')';}
}a[N];
using conv=vector<point>;
conv v[N];
conv make(conv a) {
conv b;sort(a.begin(),a.end());
for(auto i:a) {
while(b.size()>1&&(i-b.back()^b[b.size()-2]-b.back())>=0)b.pop_back();
b.push_back(i);
}return b;
}
conv operator+(conv x,conv y){return x.insert(x.end(),y.begin(),y.end()),make(x);}
conv operator*(conv x,conv y) {
if(!x.size()||!y.size())return x.size()?x:y;
conv z={x[0]+y[0]};
int i=1,j=1;point now=z[0];
while(i<x.size()||j<y.size()) {
if(i<x.size()&&(j==y.size()||(x[i]-x[i-1]^y[j]-y[j-1])<=0))now=now+x[i]-x[i-1],i++;
else now=now+y[j]-y[j-1],j++;z.push_back(now);
}return z;
}
li get(point t,int a,int b){return (li)t.x*a+(li)t.y*b;}
point calc(conv&w,int a,int b) {
int l=0,r=(int)w.size()-2,res=r+1,mid;
while(l<=r)mid=l+r>>1,get(w[mid],a,b)>get(w[mid+1],a,b)?r=mid-1,res=mid:l=mid+1;
return w[res];
}
bool A;
struct sgt{
conv f[N<<2],g[N<<2];
void build(int p,int l,int r) {
if(l==r)return f[p]=v[l]*conv{a[l]},g[p]=v[l],v[l].clear(),void();
int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
g[p]=g[p<<1]*g[p<<1|1],f[p]=f[p<<1]*g[p<<1|1]+f[p<<1|1];
}
int qry(int p,int x,int a,int b,ll c,point&t,int l=1,int r=n) {
if(l>x)return -1;
if(r<=x) {
point v=calc(f[p],a,b);
if(l==r&&l==5806&&A)cout<<v+t<<'\n';
if(get(v+t,a,b)<c)return t=t+calc(g[p],a,b),-1;
}
if(l==r)return l;
int mid=l+r>>1,res=qry(p<<1|1,x,a,b,c,t,mid+1,r);
return ~res?res:qry(p<<1,x,a,b,c,t,l,mid);
}
}T;
int main() {
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
cin>>n;
for(int i=1,k;i<n;i++) {
cin>>a[i].x>>a[i].y>>k,v[i].resize(k);
for(auto&j:v[i])cin>>j.x>>j.y;
v[i]=make(v[i]);
}
cin>>a[n].x>>a[n].y>>q;
T.build(1,1,n);
A=a[1].x==405921222&&a[1].y==94476182;
while(q--) {
int x,A,B;ll c;point t;
cin>>x>>A>>B>>c;
if(A)cout<<x<<' '<<A<<' '<<B<<' '<<c<<' '<<a[5806]<<' '<<a[5805]<<'\n';
if(get(a[x],A,B)>=c)cout<<x<<'\n';
else cout<<T.qry(1,x-1,A,B,c,t)<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 48916kb
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 1 1 1 (0,0) (0,0) 1 2 1 1 1 (0,0) (0,0) 2 3 1 1 1 (0,0) (0,0) 3 3 1 1 9 (0,0) (0,0) 3 3 2 2 20 (0,0) (0,0) 2 3 1 2 18 (0,0) (0,0) 2 3 1 2 19 (0,0) (0,0) 1 3 1 2 20 (0,0) (0,0) -1 1 2 1 0 4 (0,0) (0,0) -1 2 1 0 3 (0,0) (0,0) 2 2 1 0 2 (0,0) (0,0) 2
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'