QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473006 | #1272. Dynamic Convex Hull | grass8cow | TL | 0ms | 28372kb | C++17 | 2.6kb | 2024-07-11 20:53:11 | 2024-07-11 20:53:12 |
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];
#define pi pair<ll,ll>
#define pb push_back
vector<pi>g[400100],g2[401000];
ll X[100100];
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);
}
const int V=5e4;
int kl,kr;
pi sta[100100];
ll p4(ll x){
return x*x*x*x;
}
ll F(pi a,ll x){
return p4(a.fi-x)+a.se;
}
void sol(vector<pi>a,vector<pi>b){
sort(a.begin(),a.end());sort(b.begin(),b.end());
int as=a.size(),i=0;
kl=kr=0;
for(pi t:b){
while(i<as&&a[i].fi<=t.fi){
if(!kr)L[1]=a[i].fi,R[1]=V,sta[1]=a[i],kl=kr=1;
else{
while(R[kl]<a[i].fi)kl++;L[kl]=a[i].fi;
if(F(sta[kr],V)<=F(a[i],V))continue;
while(kl<=kr&&F(sta[kr],L[kr])>=F(a[i],L[kr]))kr--;
if(kl<=kr){
ll l=L[kr],r=R[kr];
while(l<=r){
ll mi=(l+r)>>1;
if(F(sta[kr],mi)>=F(a[i],mi))R[kr]=r=mi-1;
else l=mi+1;
}
}
sta[++kr]=a[i];
if(kl==kr)L[kr]=a[i].fi;else L[kr]=R[kr-1]+1;
R[kr]=V;
}
i++;
}
if(!kr)continue;
while(R[kl]<t.fi)kl++;L[kl]=t.fi;
ans[t.se]=min(ans[t.se],F(sta[kl],t.fi));
}
}
const ll INF=4e18;
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();
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=V+1-a.fi;
for(pi &b:g2[p])b.fi=V+1-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: 0ms
memory: 28372kb
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...