AOJ 0580 Fish

問題ページ
魚の生息範囲 | Aizu Online Judge

考えたこと

3次元imosすればよさそうだけど制約的に無理。領域木とかを考えてもわからないので解説を見たらただの座圧ではい。O(N⁴)で解ける
これくらいは思いつきたかった…

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// xx, yy, zzにそれぞれ座圧する元の配列を突っ込むとx, y, zが座圧された配列で返ってくる
// zip[座圧前] = 座圧後、unzip[座圧後] = 座圧前
VL xx, x, unzipx(100010), yy, y, unzipy(100010), zz, z, unzipz(100010);
unordered_map<int, int> zipx, zipy, zipz;
void compress() {
  x = xx;
  sort(ALL(xx));
  xx.erase(unique(ALL(xx)), xx.end());
  REP(i, xx.size()) {zipx[xx[i]] = i; unzipx[i] = xx[i];}
  REP(i, x.size()) x[i] = zipx[x[i]];
  y = yy;
  sort(ALL(yy));
  yy.erase(unique(ALL(yy)), yy.end());
  REP(i, yy.size()) {zipy[yy[i]] = i; unzipy[i] = yy[i];}
  REP(i, y.size()) y[i] = zipy[y[i]];
  z = zz;
  sort(ALL(zz));
  zz.erase(unique(ALL(zz)), zz.end());
  REP(i, zz.size()) {zipz[zz[i]] = i; unzipz[i] = zz[i];}
  REP(i, z.size()) z[i] = zipz[z[i]];
}

int dp[105][105][105];
int sx[55], sy[55], sd[55], gx[55], gy[55], gd[55];
signed main(void)
{
  int n, K;
  cin >> n >> K;
  REP(i, n) {
    cin >> sx[i] >> sy[i] >> sd[i] >> gx[i] >> gy[i] >> gd[i];
    xx.PB(sx[i]); xx.PB(gx[i]);
    yy.PB(sy[i]); yy.PB(gy[i]);
    zz.PB(sd[i]); zz.PB(gd[i]);
  }
  compress();

  REP(i, n) {
    FOR(z, zipz[sd[i]], zipz[gd[i]]) FOR(y, zipy[sy[i]], zipy[gy[i]]) FOR(x, zipx[sx[i]], zipx[gx[i]]) {
      dp[z][y][x]++;
    }
  }

  ll ret = 0;
  REP(i, z.size()) REP(j, y.size()) REP(k, x.size()) {
    if(dp[i][j][k] >= K) {
      ret += (unzipz[i+1]-unzipz[i])*(unzipy[j+1]-unzipy[j])*(unzipx[k+1]-unzipx[k]);
    }
  }

  cout << ret << endl;

  return 0;
}