QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80338 | #1272. Dynamic Convex Hull | eyiigjkn | TL | 1ms | 11712kb | C++14 | 2.7kb | 2023-02-23 14:39:00 | 2023-02-23 14:39:01 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
constexpr int N=5e4;
constexpr ll INF=9e18;
int minn[200010],hmn[20][200010];
ll ans[100010];
bool vis[20][200010];
inline ll sq(ll x){return x*x;}
inline ll pw4(ll x){return sq(x)*sq(x);}
inline void chkmin(ll &x,const ll &y){x=(x<y?x:y);}
struct Func
{
ll a,b;
Func(){}
Func(ll a,ll b):a(a),b(b){}
ll operator()(ll x)const{return pw4(x-a)+b;}
}F[200010];
struct Update
{
int l,r;
Update(){}
Update(int l,int r):l(l),r(r){}
}upd[200010];
struct Query
{
int t,x;
Query(){}
Query(int t,int x):t(t),x(x){}
}qry[100010];
void update(int rt,int l,int r,int i,bool *vis,int *hmn)
{
if(!vis[rt]) hmn[rt]=minn[rt],vis[rt]=1;
if(l==r)
{
if(!minn[rt] || F[i](l)<F[minn[rt]](l)) minn[rt]=i;
return;
}
int mid=(l+r)/2;
if(!minn[rt] || F[i](mid)<F[minn[rt]](mid)) swap(i,minn[rt]);
if(!i) return;
if(!minn[rt*2] || F[i](l)<F[minn[rt*2]](l)) update(rt*2,l,mid,i,vis,hmn);
if(!minn[rt*2+1] || F[i](r)<F[minn[rt*2+1]](r)) update(rt*2+1,mid+1,r,i,vis,hmn);
}
ll query(int rt,int l,int r,int x)
{
if(!minn[rt]) return INF;
if(l==r) return F[minn[rt]](x);
int mid=(l+r)/2;
ll ans=F[minn[rt]](x);
if(x<=mid) chkmin(ans,query(rt*2,l,mid,x));
else chkmin(ans,query(rt*2+1,mid+1,r,x));
return ans;
}
void undo(int rt,int l,int r,bool *vis,int *hmn)
{
if(!vis[rt]) return;
minn[rt]=hmn[rt];vis[rt]=0;
if(l==r) return;
int mid=(l+r)/2;
undo(rt*2,l,mid,vis,hmn);
undo(rt*2+1,mid+1,r,vis,hmn);
}
void slv(int d,int l,int r,const vi &U,const vi &Q)
{
if(l==r)
{
for(int i:U) update(1,1,N,i,vis[d],hmn[d]);
for(int i:Q) ans[i]=query(1,1,N,qry[i].x);
undo(1,1,N,vis[d],hmn[d]);
return;
}
vi Ul,Ur,Ql,Qr;
int mid=(l+r)/2;
for(int i:U)
if(l>=upd[i].l && r<=upd[i].r) update(1,1,N,i,vis[d],hmn[d]);
else
{
if(mid>=upd[i].l) Ul.push_back(i);
if(mid<upd[i].r) Ur.push_back(i);
}
for(int i:Q)
if(qry[i].t<=mid) Ql.push_back(i);
else Qr.push_back(i);
slv(d+1,l,mid,Ul,Ql);
slv(d+1,mid+1,r,Ur,Qr);
undo(1,1,N,vis[d],hmn[d]);
}
int main()
{
int T,n,m,op,t,x;
ll a,b;
cin>>T;
while(T--)
{
int q=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld",&F[i].a,&F[i].b),upd[i]=Update(1,m);
for(int i=1;i<=m;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%lld%lld",&a,&b);
F[++n]=Func(a,b);
upd[n]=Update(i,m);
}
else if(op==2) scanf("%d",&t),upd[t].r=i;
else scanf("%d",&x),qry[++q]=Query(i,x);
}
vi U(n),Q(q);
iota(U.begin(),U.end(),1);
iota(Q.begin(),Q.end(),1);
slv(0,1,m,U,Q);
for(int i=1;i<=q;i++)
if(ans[i]<INF) printf("%lld\n",ans[i]);
else puts("-1");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 11712kb
input:
1 2 8 3 9 6 100 3 4 2 1 3 4 1 1 1 3 4 2 2 2 3 3 4
output:
10 116 82 -1
result:
ok 4 lines
Test #2:
score: -100
Time Limit Exceeded
input:
5 100000 100000 39858 403048304064108142 6205 947055477496917683 788 911049878617783635 4261 626046370039242987 25008 685663359245704160 2202 848160200813297060 6216 289413959649340862 13189 722639235230562920 14820 749131972848517338 40221 716370580825502902 43025 222416883111096081 239 67541747335...
output:
8965459705354176 4971977966769926 697901276892631 137933512622231 241300695130646 69834459127665 608888490030871 275290771453117 124708297596551 528579762164961 323363278594616 68877950911521 273744439650326 288717635366668 5279149605915016 1330426007087040 1011296561114801 126582183883030 109348892...