【CF527C】Glass Carving

题面

洛谷

题解

因为横着切与纵切无关

所以开\(set\)维护横着的最大值和纵着的最大值即可

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

typedef long long ll;

int W, H, N;

set<ll> cx, cy;

multiset<ll> x, y;

multiset<ll> :: iterator ite;

int main() {

    W = gi(), H = gi(), N = gi();

    x.insert(W), y.insert(H);

    cx.insert(0), cx.insert(W);

    cy.insert(0), cy.insert(H);

    for (int i = 1; i <= N; i++) {

        char ch[5]; scanf("%s", ch);

        int t = gi();

        if (ch[0] == 'H') {

            cy.insert(t); ite = cy.find(t); --ite;

            ll l = *ite; ++ite; ++ite;

            ll r = *ite;

            ite = y.find(r - l);

            y.erase(ite); y.insert(r - t); y.insert(t - l);

        }

        else {

            cx.insert(t); ite = cx.find(t); --ite;

            ll l = *ite; ++ite; ++ite;

            ll r = *ite;

            ite = x.find(r - l);

            x.erase(ite); x.insert(r - t); x.insert(t - l);

        }

        ite = x.end(); --ite;

        ll l = *ite;

        ite = y.end(); --ite;

        printf("%I64d\n", l * (*ite));

    }

    return 0;

}