QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80338#1272. Dynamic Convex HulleyiigjknTL 1ms11712kbC++142.7kb2023-02-23 14:39:002023-02-23 14:39:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 14:39:01]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:11712kb
  • [2023-02-23 14:39:00]
  • 提交

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...

result: