mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #296 (Div. 2) C. Glass Carving

情弱故に敗北した。

問題:http://codeforces.com/problemset/problem/527/C

解法:最大の面積は(横の長さの最大長さ)×(縦の長さの最大長さ)に等しくなることに注目する。このことにより、横の長さの最大値と縦の長さの最大値をそれぞれ求めれば良いことになる。

本番ではその求め方としてsegment木を使ったが、multisetを使ったほうが楽。詳しいことはコード参照。

setのlower_boundは専用の関数を使わないと、TLEするらしい。それのせいでずっとTLEして悩んでいた。
以下ソースコード

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int main() {
    int W, H, N;
    cin >> W >> H >> N;
    set<int> h, w;
    multiset<int> mh, mw;
    h.insert(H); h.insert(0);
    w.insert(W); w.insert(0);
    mh.insert(H); mw.insert(W);
    set<int>::iterator l, r;
    while (N--) {
        char c;
        int x;
        scanf(" %c %d", &c, &x);
        if (c == 'H') {
            l = h.lower_bound(x);
            r = l; l--;
            h.insert(x);
            mh.insert((*r)-x);
            mh.insert(x-(*l));
            mh.erase(mh.find((*r)-(*l)));
        } else {
            l = w.lower_bound(x);
            r = l; l--;
            w.insert(x);
            mw.insert((*r)-x);
            mw.insert(x-(*l));
            mw.erase(mw.find((*r)-(*l)));
        }
        ll ans = ((ll)(*mh.rbegin()) * (*mw.rbegin()));
        printf("%lld\n", ans);
    }
    return 0;
}