QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464060#8525. Mercenarieszwh2008Compile Error//C++142.8kb2024-07-05 18:32:222024-07-05 18:32:22

Judging History

你现在查看的是最新测评结果

  • [2024-07-05 18:32:22]
  • 评测
  • [2024-07-05 18:32:22]
  • 提交

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;
}
ll get(point t,int a,int b){return t.x*a+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;
    if(AA&&w[res].x==217804443)cout<<w[res+1]<<'\n'<<w[res+2]<<'\n';
    return w[res];
}
bool AA;
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&&AA)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);
    AA=a[1].x==405921222&&a[1].y==94476182;
    while(q--) {
        int x,A,B;ll c;point t;
        cin>>x>>A>>B>>c;
        if(AA)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;
}

详细

answer.code: In function ‘point calc(conv&, int, int)’:
answer.code:40:8: error: ‘AA’ was not declared in this scope
   40 |     if(AA&&w[res].x==217804443)cout<<w[res+1]<<'\n'<<w[res+2]<<'\n';
      |        ^~