Codeforces 1010E. Store(KDT)

Author Avatar
Sakits 7月 28, 2018

题解

  这场CF居然连1E都这么水…裸三维数点…当作KDT练练手吧
  首先很容易求出最小的长方体,然后查一下这个长方体里有没有那mm个点就可以判有无解。
  每次查询某个点的话先判断是否在最小长方体里,不在的话就把长方体扩展到包含那个点,再查询长方体里是否有那个mm个点即可。
  因为只要判有无点,所以KDT可以上启发式操作,跑的飞快。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define lt tr[x].ls
#define rt tr[x].rs
#define maxs(a, b) a=(a>b?a:b)
#define mins(a, b) a=(a<b?a:b)
using namespace std;
const int maxn=500010, inf=1e9;
struct kdt{int d[3], l[3], r[3], ls, rs, size;}tr[maxn];
struct poi{int d[3];}P, np[maxn], L, R;
struct que{int l[3], r[3];}q;
int n, m, K, cmpd, tott, root, ans;

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

bool operator < (poi a, poi b){return a.d[cmpd]<b.d[cmpd];}

inline void newnode(int x)
{
	tr[x].size=1;
	for(int i=0;i<3;i++)
	tr[x].d[i]=tr[x].l[i]=tr[x].r[i]=P.d[i];
}

inline void up(int x)
{
	tr[x].size=tr[lt].size+tr[rt].size+1;
	for(int i=0;i<3;i++)
	{
		if(lt) mins(tr[x].l[i], tr[lt].l[i]), maxs(tr[x].r[i], tr[lt].r[i]);
		if(rt) mins(tr[x].l[i], tr[rt].l[i]), maxs(tr[x].r[i], tr[rt].r[i]);
	}
}

void build(int &x, int l, int r, int ty)
{
	x=++tott; int mid=(l+r)>>1; cmpd=ty;
	nth_element(np+l, np+mid, np+r+1); 
	P=np[mid]; newnode(x);
	if(l<mid) build(lt, l, mid-1, (ty==2)?0:(ty+1));
	if(mid<r) build(rt, mid+1, r, (ty==2)?0:(ty+1));
	up(x);
}

inline bool check(int x)
{
	for(int i=0;i<3;i++)
	if(tr[x].l[i]<q.l[i] || tr[x].r[i]>q.r[i]) return 0;
	return 1;
}

inline bool cover(int x)
{
	for(int i=0;i<3;i++)
	if(tr[x].d[i]<q.l[i] || tr[x].d[i]>q.r[i]) return 0;
	return 1;
}

inline bool cross(int x)
{
	if(!x) return 0;
	for(int i=0;i<3;i++)
	if(tr[x].l[i]>q.r[i] || tr[x].r[i]<q.l[i]) return 0;
	return 1; 
}

void query(int x)
{
	if(ans) return;
	if(check(x)) {ans=1; return;}
	if(cover(x)) {ans=1; return;}
	if(cross(lt)) query(lt);
	if(cross(rt)) query(rt);
}
 
int main()
{
	for(int i=0;i<3;i++) read(L.d[i]), R.d[i]=1;
	read(n); read(m); read(K);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++) 
		read(P.d[j]), L.d[j]=min(L.d[j], P.d[j]), R.d[j]=max(R.d[j], P.d[j]);
	}
	for(int i=1;i<=m;i++) for(int j=0;j<3;j++) read(np[i].d[j]);
	build(root, 1, m, 0);
	for(int j=0;j<3;j++) 
	q.l[j]=L.d[j], q.r[j]=R.d[j];
	ans=0; query(root);
	if(ans) return puts("INCORRECT"), 0;
	puts("CORRECT");
	while(K--)
	{
		int flag=0;
		for(int j=0;j<3;j++) 
		{
			read(P.d[j]);
			if(P.d[j]>R.d[j] || P.d[j]<L.d[j]) flag=1;
		}
		if(!flag) puts("OPEN");
		else
		{
			for(int j=0;j<3;j++) 
			q.l[j]=min(L.d[j], P.d[j]), 
			q.r[j]=max(R.d[j], P.d[j]);
			ans=0; query(root);
			if(ans) puts("CLOSED");
			else puts("UNKNOWN");
		}
	}
}