JOI 春合宿 2008 day3-1 Origami (2Q, 難易度 6)

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

• ジャッジへのリンク
• 問題文へのリンク

問題概要

のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は

• 
• 

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

制約

• 
• 
• 
• 

考えたこと

いかにも

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

という問題に見える。しかしこれだと、 の計算量となって、TLE もするし MLE もするようだ。 という制約が絶妙っぽい。

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

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

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

std::map を用いた場合、 程度として、計算量は となる。

コード

#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;
}