백준2574 마법색종이

작성일 | In

문제 링크

  • http://icpc.me/2574

문제 출처

  • 2006 KOI 초등부 3번

사용 알고리즘

  • 분할 정복
  • 2D 세그먼트 트리

시간복잡도

  • $O(N \log^2 X)$

풀이

색종이를 자르는 것에 따라 분할 정복을 하면 된다는 것은 쉽게 생각할 수 있습니다.

분할된 조각에서 다음 분할 지점을 빠르게 찾는 것이 문제입니다.
이 작업은 2D Segment Tree에서 최솟값을 찾는 것으로 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

const int MX = 40404;
struct Node1{
    int l, r, v;
    Node1() : l(-1), r(-1), v(1e9) {}
} nd[10101010]; int pv;

struct Node2{
    int l, r, root;
    Node2() : l(-1), r(-1), root(-1) {}

    void update(int node, int s, int e, int x, int v){
        if (s == e){ nd[node].v = v; return; }
        int m = s + e >> 1, mn = 1e9;
        if (x <= m){
            if (nd[node].l == -1) nd[node].l = ++pv;
            update(nd[node].l, s, m, x, v);
            mn = min(mn, nd[nd[node].l].v);
            if (nd[node].r != -1) mn = min(mn, nd[nd[node].r].v);
        }
        else{
            if (nd[node].r == -1) nd[node].r = ++pv;
            update(nd[node].r, m + 1, e, x, v);
            mn = min(mn, nd[nd[node].r].v);
            if (nd[node].l != -1) mn = min(mn, nd[nd[node].l].v);
        }
        nd[node].v = mn;
    }
    int query(int node, int s, int e, int l, int r){
        if (node == -1) return 1e9;
        if (r < s || e < l) return 1e9;
        if (l <= s && e <= r) return nd[node].v;
        int m = s + e >> 1;
        return min(query(nd[node].l, s, m, l, r), query(nd[node].r, m + 1, e, l, r));
    }
    void update(int x, int v){
        if (root == -1) root = ++pv;
        update(root, 0, MX, x, v);
    }
    int query(int l, int r){
        return query(root, 0, MX, l, r);
    }
} nd2[1 << 17]; int pv2;

struct Seg2{
    int root = 0;
    void update(int node, int s, int e, int x, int y, int v){
        if (s == e){ nd2[node].update(y, v); return; }
        int m = s + e >> 1, mn = 1e9;
        if (x <= m){
            if (nd2[node].l == -1) nd2[node].l = ++pv2;
            update(nd2[node].l, s, m, x, y, v);
            mn = min(mn, nd2[nd2[node].l].query(y, y));
            if (nd2[node].r != -1) mn = min(mn, nd2[nd2[node].r].query(y, y));
        }
        else{
            if (nd2[node].r == -1) nd2[node].r = ++pv2;
            update(nd2[node].r, m + 1, e, x, y, v);
            mn = min(mn, nd2[nd2[node].r].query(y, y));
            if (nd2[node].l != -1) mn = min(mn, nd2[nd2[node].l].query(y, y));
        }
        nd2[node].update(y, mn);
    }
    int query(int node, int s, int e, int l, int r, int L, int R){
        if (node == -1) return 1e9;
        if (r < s || e < l) return 1e9;
        if (l <= s && e <= r) return nd2[node].query(L, R);
        int m = s + e >> 1;
        return min(query(nd2[node].l, s, m, l, r, L, R), query(nd2[node].r, m + 1, e, l, r, L, R));
    }
    void update(int x, int y, int v){
        update(root, 0, MX, x, y, v);
    }
    int query(int l, int r, int L, int R){
        return query(root, 0, MX, l, r, L, R);
    }
} seg;

int n, m, k;
p a[30303];

p solve(int x, int xx, int y, int yy, int dir){
    int nxt = seg.query(x+1, xx-1, y+1, yy-1);
    if(nxt == 1e9){
        ll t = (xx-x) * (yy-y);
        return p(t, t);
    }
    p t1, t2;
    if(dir == 0) t1 = solve(x, xx, y, a[nxt].y, 1), t2 = solve(x, xx, a[nxt].y, yy, 1);
    if(dir == 1) t1 = solve(x, a[nxt].x, y, yy, 0), t2 = solve(a[nxt].x, xx, y, yy, 0);
    return p(min(t1.x, t2.x), max(t1.y, t2.y));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    for(int i=1; i<=k; i++){
        cin >> a[i].x >> a[i].y;
        seg.update(a[i].x, a[i].y, i);
    }
    auto t = solve(0, n, 0, m, 0);
    cout << t.y << " " << t.x;
}