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"; }