题解：CF1010E Store

提供一种

O(n\log n)

的做法。

注意到题目等价于找一个有限空间内的三维长方体，所以第一类点（即第一次输入的点，下同）能够框定该长方体的最小形状，而第二类则要求其不覆盖某些位置，前者是好利用的，求出长方体最小形状之后可以通过判断第二类点和查询点是否在内部判断无解或必然可行。

而必然不可行等价于最小形状并上查询点之后内部存在第二类点，这个东西可以直接静态三维数点维护，这里主要讲一下怎么优化。

注意到我们不在意内部的点的个数，只在意是否存在。而查询一个三维前缀内是否存在数点，等价于二维数点的最值，从而做到

O(n\log n)

。具体的，注意到新长方体一定有一个顶点没有变化，枚举这个顶点，将其作为坐标原点，此时构成了

O(1)

种（具体而言，8 种）前缀。对于第二类点，也可以类似地加入这些前缀中。

更进一步的，如果我们对于数点所在的方位进行分讨，可以使修改常数降至 1，进一步优化算法。

这里给出的是前一种实现，时间复杂度

O(n\log n)

。

CPP

#include<bits/stdc++.h>
#define maxn 370005
#define fi first
#define se second
inline int max(int x,int y){return x<y?y:x;}
using namespace std;
const int inf=1e9+7;

int X,Y,Z,n,m,k,ans[maxn];
struct node{
	int x,y,z;
	node():x(0),y(0),z(0){}
	node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
	bool operator ==(node d){return x==d.x&&y==d.y&&z==d.z;}
	node operator +(node d){return node(max(x,d.x),max(y,d.y),max(z,d.z));}
	int operator [](int p){return (p==0?x:(p==1?y:z));}
}r[2],cur[2];
vector<pair<node,int> >t[8];
struct BIT{
	int t[maxn];
	void update(int x,int k){for(int i=x;i<=Y;i+=i&-i) t[i]=min(t[i],k);}
	int query(int x){
		int res=inf;
		for(int i=x;i;i-=i&-i) res=min(res,t[i]);
		return res;
	}
	void clear(){for(int i=1;i<=Y;i++) t[i]=inf;}
}T;
void solve(vector<pair<node,int> >vec){
	T.clear();
	sort(vec.begin(),vec.end(),[](pair<node,int> p1,pair<node,int> p2){
		return (p1.fi.x==p2.fi.x?p1.se<p2.se:p1.fi.x<p2.fi.x);
	});
	for(auto i:vec){
		node cur=i.fi;
		int id=i.se;
		if(!id)	T.update(cur.y,cur.z);
		else ans[id]=T.query(cur.y)<=cur.z;
	}
}
inline void solve(){
	r[0]=r[1]=node(-inf,-inf,-inf);
	scanf("%d%d%d%d%d%d",&X,&Y,&Z,&n,&m,&k);
	for(int i=1,x,y,z;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		r[0]=r[0]+node(X+1-x,Y+1-y,Z+1-z);
		r[1]=r[1]+node(x,y,z);
	}
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		cur[0]=r[0]+node(X+1-x,Y+1-y,Z+1-z),cur[1]=r[1]+node(x,y,z);
		if(cur[0]==r[0]&&cur[1]==r[1]) return puts("INCORRECT"),void();
		for(int j=0;j<8;j++){
			node tmp=node(cur[j&1][0],cur[(j>>1)&1][1],cur[(j>>2)&1][2]);
			if(tmp==node(r[j&1][0],r[(j>>1)&1][1],r[(j>>2)&1][2])) t[j].emplace_back(node(cur[~j&1][0],cur[(~j>>1)&1][1],cur[(~j>>2)&1][2]),0);
		}
	}
	puts("CORRECT");
	for(int i=1,x,y,z;i<=k;i++){
		scanf("%d%d%d",&x,&y,&z);
		cur[0]=r[0]+node(X+1-x,Y+1-y,Z+1-z),cur[1]=r[1]+node(x,y,z);
		if(cur[0]==r[0]&&cur[1]==r[1]){
			ans[i]=-1;
			continue;
		}
		for(int j=0;j<8;j++){
			node tmp=node(cur[j&1][0],cur[(j>>1)&1][1],cur[(j>>2)&1][2]);
			if(tmp==node(r[j&1][0],r[(j>>1)&1][1],r[(j>>2)&1][2])){
				t[j].emplace_back(node(cur[~j&1][0],cur[(~j>>1)&1][1],cur[(~j>>2)&1][2]),i);
				break;
			}
		}
	}
	for(int i=0;i<8;i++) solve(t[i]);
	for(int i=1;i<=k;i++)
	 if(ans[i]==-1) puts("OPEN");
	 else puts(ans[i]?"CLOSED":"UNKNOWN");
}
signed main(){
	signed T=1;
	while(T--) solve();
	return 0;
}

文章操作

相关推荐

评论

题解：CF1010E Store