AOJ_0580 Fish

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580

解法
3次元空間での座標圧縮。圧縮後と圧縮前の値の変換が出来るようにして圧縮する。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

typedef long long ll;
int N, K;
ll x1[50], y1[50], z1[50], x2[50], y2[50], z2[50];
int a[101][101][101];
set<ll> X, Y, Z;
vector<ll> xx, yy, zz;
int main(){
	scanf("%d %d", &N, &K);
	for(int i = 0; i < N; i++){
		scanf("%lld %lld %lld %lld %lld %lld", &x1[i], &y1[i], &z1[i], &x2[i], &y2[i], &z2[i]);
		X.insert(x1[i]); X.insert(x2[i]);
		Y.insert(y1[i]); Y.insert(y2[i]);
		Z.insert(z1[i]); Z.insert(z2[i]);
	}
	int i = 0;
	for(set<ll>::iterator it = X.begin(); i < X.size(); it++, i++)
		xx.push_back(*it);
	i=0;
	for(set<ll>::iterator it = Y.begin(); i < Y.size(); it++, i++)
		yy.push_back(*it);
	i=0;
	for(set<ll>::iterator it = Z.begin(); i < Z.size(); it++, i++)
		zz.push_back(*it);
	for(i = 0; i < N; i++){
		int sx = distance(xx.begin(), lower_bound(xx.begin(), xx.end(), x1[i]) );
		int sy = distance(yy.begin(), lower_bound(yy.begin(), yy.end(), y1[i]) );
		int sz = distance(zz.begin(), lower_bound(zz.begin(), zz.end(), z1[i]) );
		int tx = distance(xx.begin(), lower_bound(xx.begin(), xx.end(), x2[i]) );
		int ty = distance(yy.begin(), lower_bound(yy.begin(), yy.end(), y2[i]) );
		int tz = distance(zz.begin(), lower_bound(zz.begin(), zz.end(), z2[i]) );
		for(int x = sx; x < tx; x++)
			for(int y = sy; y < ty; y++)
				for(int z = sz; z < tz; z++)
					a[x][y][z]++;
	}
	ll V = 0;
	for(int x = 0; x < 101; x++)
		for(int y = 0; y < 101; y++)
			for(int z = 0; z < 101; z++)
				if(a[x][y][z] >= K)
					V += (xx[x+1] - xx[x]) * (yy[y+1] - yy[y]) * (zz[z+1] - zz[z]);
	printf("%lld\n", V);
	return 0;
}