一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。

問題概要

$H \times W$ のグリッド上に $N$ 枚の長方形の紙を敷いていく。 $i$ 枚目の紙は

$x = p_{i}, p_{i}+1, \dots, r_{i}$
$y = q_{i}, q_{i}+1, \dots, s_{i}$

を満たす座標 $(x, y)$ を覆う領域に配置される。最も多くの紙が重なっているマスでは何枚重なっているか、および、そのようなマスが何マスあるのかを数え上げよ。

制約

$1 \le N \le 5000$
$1 \le H, W \le 10^{6}$
$0 \le r_{i} - p_{i} \le 20$
$0 \le s_{i} - q_{i} \le 20$

考えたこと

いかにも

座標圧縮することで、 $2N \times 2N$ 程度のグリッドだとみなして
二次元いもす法をする

という問題に見える。しかしこれだと、 $O(N^{2} \log N)$ の計算量となって、TLE もするし MLE もするようだ。 $N \le 5000$ という制約が絶妙っぽい。

一枚一枚の長方形が小さい

そこで別の作戦を立てよう。今回は制約条件から、1 枚 1 枚の長方形の紙の大きさが最大でも $20 \times 20 = 400$ 程度のようだ。よって、長方形の紙が覆う領域を 1 マスずつ愚直にカウントしていってよい。座標圧縮なんて要らなかった。

ただし $H \times W$ の領域をメモリにおさめるわけにはいかないので、必要なところだけメモリにおさめる。具体的には std::map などの廉造配列を用いれば OK。

std::map を用いた場合、 $V = 400$ 程度として、計算量は $O(NV(\log N + \log V))$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;
#define REP(i, n) for (long long i = 0; i < (long long)(n); ++i)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); ++i)

int main() {
    int N, H, W;
    cin >> N >> H >> W;
    map<pint,int> fi;
    REP(i, N) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1;
        REP2(x, x1, x2) REP2(y, y1, y2) fi[pint(x, y)]++;
    }
    int res = 0, area = 0;
    for (auto it : fi) {
        if (res < it.second) res = it.second, area = 1;
        else if (res == it.second) ++area;
    }
    cout << res << endl << area << endl;
}