백준20180 Two Buildings

작성일 | In

문제 링크

  • http://icpc.me/20180

문제 출처

  • 2020 서울 리저널 L번

사용 알고리즘

  • 분할 정복 최적화

시간복잡도

  • $O(N \log N)$

풀이

$i, j$를 적절히 선택해 $(i, H_i)$와 $(i, -H_j)$가 꼭짓점인 직사각형의 넓이를 최대화하는 문제입니다.

2017 ACM-ICPC World Finals D번 Money for Nothing과 동일한 문제가 됩니다. (풀이)

전체 코드

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
#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<ll, ll> p;

int n;
vector<p> a, b, _a, _b;

ll mx;
void f(int s, int e, int l, int r){
    if(s > e) return;
    int m = s + e >> 1;
    ll ret = -4e18, k = s;
    for(int i=l; i<=r; i++){
        ll dx = b[i].x - a[m].x;
        ll dy = b[i].y - a[m].y;
        ll now = (dx < 0 && dy < 0) ? 0 : dx * dy;
        if(now > ret) ret = now, k = i;
    }
    f(s, m-1, l, k); f(m+1, e, k, r);
    mx = max(mx, ret);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        _a.emplace_back(i, -x);
        _b.emplace_back(i, x);
    }
    sort(all(_a)); sort(all(_b), greater<>());
    a.reserve(n); b.reserve(n);
    for(auto i : _a) if(a.empty() || a.back().y > i.y) a.push_back(i);
    for(auto i : _b) if(b.empty() || b.back().y < i.y) b.push_back(i);
    reverse(all(b));
    f(0, a.size()-1, 0, b.size()-1);
    cout << mx;
}