JOI2012春day1-2: 魚

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/

setを使う問題といえばコレ。直方体の体積を断面図を考えて求めていく問題です。

こういう問題でsetを使う際、
(1)番兵を使うと便利。
(2)lb,ubを覚えてまとめてerase(lb,ub)する。
(3)ある要素を見つけてそこからincrement or decrementする感じ。
かな?
ほとんどAlgoogleさんのコードと同じです。
JOI 春合宿 2012 Fish - Algoogle

struct cube {
	int p[3];
	cube(int x, int y, int z) { p[0] = x, p[1] = y, p[2] = z; }
	cube() { p[0] = p[1] = p[2] = 0;}
	friend ostream& operator<<(ostream& out, const cube& c){
		out << "(" << c.p[0] << ", " << c.p[1] << ", " << c.p[2] << ")"; return out; }
	bool operator<(const cube& c) { return p[2] > c.p[2]; }
};

int N;
char RGB[3] = {'R', 'G', 'B'};
pi P[MAX_N];
cube C[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int a; char c;
		cin >> a >> c;
		int b = 0;
		while(RGB[b] != c) b++;
		P[i] = pi(a, b);
	}
	sort(P, P + N);
	cube c(1, 1, 1);
	int r = 0;
	rep(i, 0, N) {
		while(r != N && P[r].fst - P[i].fst * 2 < 0) {
			c.p[P[r].sec]++;
			r++;
		}
		C[i] = c;
		c.p[P[i].sec]--;
	}
	C[N] = cube(0, 0, 0);
	sort(C, C + N + 1);

	ll ans = 0;
	ll area = 0, pz = inf;
	set<pi> s = {pi(0, inf), pi(inf, 0)};

	rep(i, 0, N + 1) {
		ll x = C[i].p[0], y = C[i].p[1], z = C[i].p[2];
		if(i != 0) ans += area * (pz - z);
		pz = z;
		set<pi>::iterator lb = s.lower_bound(pi(x, y)), ub = lb;
		int px = x, py = (*lb).sec;
		if(py >= y) continue;
		while(lb != s.begin()) {
			lb--;
			int nx = (*lb).fst, ny = (*lb).sec;
			area += 1LL * (px - nx) * (y - py);
			if(ny > y) break;
			px = nx; py = ny;
		}
		lb++;
		s.erase(lb, ub);
		s.insert(ub, pi(x, y));
	}
	cout << ans - 1 << "\n";
}