第12回日本情報オリンピック 予選 問題5 魚の生息範囲 (Fish) AOJ0580

結構昔に「わかんねっ」っていって放置してた問題。

座標圧縮

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n,m;
ll ans;
ll d[52][7];
ll sx[110],sy[110],sd[110];
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 6;j++){
			scanf("%lld",&d[i][j]);
			switch(j%3){
				case 0:
					sx[i*2+(j/3)] = d[i][j];
					break;
				case 1:
					sy[i*2+(j/3)] = d[i][j];
					break;
				case 2:
					sd[i*2+(j/3)] = d[i][j];
					break;
			}
		}
	}
	sort(sx,sx + 2*n);
	sort(sy,sy + 2*n);
	sort(sd,sd + 2*n);

	int six=2*n,siy=2*n,sid=2*n;
	int cnt = 0;
	int pre = sx[cnt++];
	for(int i = 1;i < 2*n;i++){
		if(pre != sx[i]){
			sx[cnt++] = sx[i];
			pre = sx[i];
		}
	}
	six = cnt; cnt = 0; pre = sy[cnt++]; 
	for(int i = 1;i < 2*n;i++){
		if(pre != sy[i]){
			sy[cnt++] = sy[i];
			pre = sy[i];
		}
	}
	siy = cnt; cnt = 0; pre = sd[cnt++];
	for(int i = 1;i < 2*n;i++){
		if(pre != sd[i]){
			sd[cnt++] = sd[i];
			pre = sd[i];
		}
	}
	sid = cnt;
	n = 2*n;
	for(int i = 0;i < six-1;i++){
		for(int j = 0;j < siy-1;j++){
			for(int k = 0;k < sid-1;k++){
				int co = 0;
				for(int l = 0;l < n/2;l++){
					if(sx[i] < d[l][0] || sx[i+1] > d[l][3] || sy[j] < d[l][1] || sy[j+1] > d[l][4] || sd[k] < d[l][2] || sd[k+1] > d[l][5])continue;
					co++;
				}
				if(co >= m)ans += (sx[i+1]-sx[i])*(sy[j+1]-sy[j])*(sd[k+1]-sd[k]);
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}