QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473084 | #1272. Dynamic Convex Hull | grass8cow | RE | 3ms | 27584kb | C++17 | 2.4kb | 2024-07-11 21:45:14 | 2024-07-11 21:45:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
int L[200100],R[201000];
#define ll long long
#define fi first
#define se second
ll a[200010],b[201000],ans[101000],X[100100];
#define pi pair<ll,ll>
#define pb push_back
vector<pi>g[400100],g2[401000];
void up(int p,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){g[p].pb({a[z],b[z]});return;}
int mi=(l+r)>>1;
if(x<=mi)up(p<<1,l,mi,x,y,z);
if(y>mi)up(p<<1|1,mi+1,r,x,y,z);
}
void up2(int p,int l,int r,int x){
g2[p].pb({X[x],1ll*x});if(l==r)return;int mi=(l+r)>>1;
if(x<=mi)up2(p<<1,l,mi,x);
else up2(p<<1|1,mi+1,r,x);
}
ll p4(ll x){
return x*x*x*x;
}
const ll INF=4e18;
ll F(pi a,ll x){
return p4(a.fi-x)+a.se;
}
void cdq(int pl,int pr,int l,int r,vector<pi>&a,vector<pi>&b){
if(pl>pr||l>r)return;
int mi=(l+r)>>1,jr=-1;ll nf=INF;
//assert(a[pl].fi<=b[mi].fi);
//assert(a[pl].fi<=b[l].fi);
for(int i=pl;i<=pr;i++){
if(a[i].fi>b[mi].fi)break;
ll fe=F(a[i],b[mi].fi);
assert(fe<INF);
if(nf>fe)nf=fe,jr=i;
}
ans[b[mi].se]=min(ans[b[mi].se],nf);
cdq(pl,jr,l,mi-1,a,b),cdq(jr,pr,mi+1,r,a,b);
}
void sol(vector<pi>&a,vector<pi>&b){
sort(a.begin(),a.end());sort(b.begin(),b.end());
int z=0;while(z<b.size()&&b[z].fi<a[0].fi)z++;
if(z==b.size())return;
assert(b[z].fi>=a[0].fi);
for(int i=0;i+1<b.size();i++)
assert(b[i].fi<=b[i+1].fi);
for(int i=0;i+1<a.size();i++)
assert(a[i].fi<=a[i+1].fi);
cdq(0,a.size()-1,z,b.size()-1,a,b);
}
void sol(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),L[i]=1,R[i]=m;
for(int i=1;i<=m*4;i++)g[i].clear(),g2[i].clear();
for(int i=1,op;i<=m;i++){
scanf("%d",&op);
X[i]=0;
if(op==1){n++;scanf("%lld%lld",&a[n],&b[n]);L[n]=i,R[n]=m;}
if(op==2){int x;scanf("%d",&x);R[x]=i;}
if(op==3)scanf("%lld",&X[i]),up2(1,1,m,i),ans[i]=INF;
}
for(int i=1;i<=n;i++)up(1,1,m,L[i],R[i],i);
for(int p=1;p<=m*4;p++)if(!g[p].empty()&&!g2[p].empty()){
sol(g[p],g2[p]);
for(pi &a:g[p])a.fi=-a.fi;
for(pi &b:g2[p])b.fi=-b.fi;
sol(g[p],g2[p]);
}
for(int i=1;i<=m;i++)if(X[i]){
if(ans[i]==INF)puts("-1");
else printf("%lld\n",ans[i]);
}
}
int main(){
int T;scanf("%d",&T);while(T--)sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 27584kb
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
Runtime Error
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...