17555번: Blurred Pictures

All the non-blurred pixels are connected in such a way that any horizontal or vertical line drawn between two non-blurred pixels goes only through non-blurred pixels.

 

4개의 위치 (a, b) (a, d) (c, b) (c, d)가 채워져 있으면 이 4개의 위치에 해당되는 정사각형은 모두 채워져 있다는 사실을 알 수 있다.

 

이제 정답에 대해 parametric search를 하면 된다. \(O(N\log N)\)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<pi> pic(n);
    for (int i = 0; i < n; i++) cin >> pic[i].first >> pic[i].second;
    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        bool good = false;
        for (int i = 0; i <= n - mid; i++) {
            int left = max(pic[i].first, pic[i + mid - 1].first);
            if (left + mid - 1 <= pic[i].second && left + mid - 1 <= pic[i + mid - 1].second) {good = true; break;}
        }
        if (good) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}