これこそシュタインズ・ゲートの选択だ

[noi2019]弹跳

[noi2019]弹跳

不知道有没有原题,给人一种非常原题的感觉
因为这个题学了kd-tree,然后就是板题了

#include<bits/stdc++.h>
using namespace std;
const int N=70005,inf=0x3f3f3f3f;
inline int read(){
	int s=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s;
}
struct P{
	int x,y;
}b[N],p[N];
inline bool cmp1(const int & x,const int & y){return b[x].x<b[y].x;}
inline bool cmp2(const int & x,const int & y){return b[x].y<b[y].y;}
int ls[N],rs[N],L[N],R[N],U[N],D[N],id[N],kon[N];
int mn[N],mx[N];
int vis[N],val[N],tag[N];
int tot=0,rt;
inline void maintain(int x){
	if(vis[x]) L[x]=D[x]=mn[x]=inf,R[x]=U[x]=mx[x]=-inf;
	else L[x]=R[x]=p[x].x,D[x]=U[x]=p[x].y,mn[x]=mx[x]=val[x];
	if(ls[x]) {
		L[x]=min(L[x],L[ls[x]]),R[x]=max(R[x],R[ls[x]]);
		D[x]=min(D[x],D[ls[x]]),U[x]=max(U[x],U[ls[x]]);
		mn[x]=min(mn[x],mn[ls[x]]),mx[x]=max(mx[x],mx[ls[x]]);
	}
	if(rs[x]) {
		L[x]=min(L[x],L[rs[x]]),R[x]=max(R[x],R[rs[x]]);
		D[x]=min(D[x],D[rs[x]]),U[x]=max(U[x],U[rs[x]]);
		mn[x]=min(mn[x],mn[rs[x]]),mx[x]=max(mx[x],mx[rs[x]]);
	}
}
inline int build(int l,int r){
	if(l>r) return 0;
	int mid=(l+r)>>1,x=++tot;
	double av1=0,av2=0,va1=0,va2=0;
	for(int i=l;i<=r;i++) av1+=p[kon[i]].x,av2+=p[kon[i]].y;
	av1/=(r-l+1),av2/=(r-l+1);
	for(int i=l;i<=r;i++) va1+=(av1-p[kon[i]].x)*(av1-p[kon[i]].x),va2+=(av2-p[kon[i]].y)*(av2-p[kon[i]].y);
	if(va1>va2) nth_element(kon+l,kon+mid,kon+r+1,cmp1);
	else nth_element(kon+l,kon+mid,kon+r+1,cmp2);
	p[x]=b[kon[mid]];
	val[x]=tag[x]=inf;id[x]=kon[mid];
	if(id[x]==1) val[x]=0;
	ls[x]=build(l,mid-1);rs[x]=build(mid+1,r);
	maintain(x);
	return x;
}
inline void put_tag(int x,int v){
	if(v<mx[x]&&v<tag[x]){
		tag[x]=mx[x]=v;
		mn[x]=min(mn[x],v);
		if(!vis[x]) val[x]=min(val[x],v);
	}
}
inline void push_down(int x){
	if(tag[x]==inf) return;
	if(ls[x]) put_tag(ls[x],tag[x]);
	if(rs[x]) put_tag(rs[x],tag[x]);
	tag[x]=inf;
}
inline int del(int x,int v){
	push_down(x);
	if(!vis[x]&&v==val[x]) {vis[x]=1;maintain(x);return x;}
	if(ls[x]&&v==mn[ls[x]]) {
		int t=del(ls[x],v);
		maintain(x);
		return t;
	}else {
		int t=del(rs[x],v);
		maintain(x);
		return t;
	}
}
inline void modify(int x,int v,int l,int r,int d,int u){
	push_down(x);
	if(v>=mx[x]) return;
	if(l>R[x]||r<L[x]||d>U[x]||u<D[x]) return;
	if(l<=L[x]&&r>=R[x]&&d<=D[x]&&u>=U[x]){put_tag(x,v);return;}
	if(!vis[x]&&l<=p[x].x&&p[x].x<=r&&d<=p[x].y&&p[x].y<=u)
		val[x]=min(val[x],v);
	if(ls[x]) modify(ls[x],v,l,r,d,u);
	if(rs[x]) modify(rs[x],v,l,r,d,u);
	maintain(x);
}
struct edge{
	int l,r,d,u,w;
};
vector<edge> G[N];
int n,m,w,h,dis[N];
int main(){
	n=read(),m=read(),w=read(),h=read();
	for(int i=1;i<=n;i++) kon[i]=i;
	for(int i=1;i<=n;i++) b[i].x=read(),b[i].y=read();
	for(int i=1;i<=m;i++){
		int p=read(),t=read(),l=read(),r=read(),d=read(),u=read();
		G[p].push_back({l,r,d,u,t});
	}
	rt=build(1,n);
	for(int i=1;i<=n;i++){
		int x=del(rt,mn[rt]),u=id[x];
		dis[u]=val[x];
		for(edge e:G[u]){
			modify(rt,dis[u]+e.w,e.l,e.r,e.d,e.u);
		}
	}
	for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
	return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注