CF 527C Glass Carving ( STL set )

Problem - C - Codeforces
The key is to realize that the largest area is the largest width * largest height. They can be maintained with STL set / multiset separately. For each of them, prepare a set to keep record of the existing lines. When a new line is inserted, modify around the two lines that close the new line and their interval in a multiset.

#include <bits/stdc++.h>
using namespace std;
const int MAXW = 2e5 + 5;
const int MAXH = 2e5 + 5;
const int MAXN = 2e5 + 5;

int w, h, n;

void addLine(set<int> &s, multiset<int, greater<int> > &sv, int x){
    set<int>::iterator it, jt;
    it = jt = s.lower_bound( x );
    sv.erase( sv.find( *jt - *--it ) );
    sv.insert( *jt - x );
    sv.insert( x - *it );
    s.insert( x );
}

int main(){
    scanf("%d%d%d", &w, &h, &n);
    set<int> ws, hs;
    multiset<int, greater<int> > wv, hv;
    ws.insert( 0 ), ws.insert( w );
    hs.insert( 0 ), hs.insert( h );
    wv.insert( w ), hv.insert( h );
    for(int i = 0; i < n; ++i){
        char op[3]; scanf("%s", op);
        int x; scanf("%d", &x);
        if( op[0] == 'V' ) addLine( ws, wv, x );
        else addLine( hs, hv, x );
        cout << 1LL * ( *wv.begin() ) * ( *hv.begin() ) << endl;
    }
    return 0;
}