POJ 3277 City Horizon

解法

まずは、座標圧縮する
ビルの開始点、終了点に高さをメモする
座標の小さい点から走査していき、ビルの開始点ではそのビルの高さを集合に加え、終了点では集合から削除する
高さの集合の管理には追加、削除が高速にできるものを使うと良い
追加、削除がO(logn)のデータ構造を使うと、計算量はO(nlogn)

multisetを使うと実装が楽になるが、TLEしたのでpriority_queue + カウンタ(num)で書き直した

ソースコード

int main()
{
    const int M = 4 * ten(4);
    int n;
    int a[M], b[M], h[M]; // [a, b)
    scanf("%d", &n);
    rep(i, n)
	scanf("%d%d%d", a + i, b + i, h + i);

    vector<int> pos;
    rep(i, n)
	pos.pb(a[i]), pos.pb(b[i]);
    uniq(pos);

    vector<int> uh(h, h + n);
    uniq(uh);

    static vector<int> start[2 * M], end[2 * M];
    rep(i, n)
    {
	int s = lower_bound(all(pos), a[i]) - pos.begin();
	int e = lower_bound(all(pos), b[i]) - pos.begin();
	int hi = lower_bound(all(uh), h[i]) - uh.begin();
	start[s].pb(hi);
	end[e].pb(hi);
    }

    int num[M] = {};
    priority_queue<pint> h_set;	// (height, hi)
    ll area = 0;
    rep(pi, pos.size())
    {
	rep(i, start[pi].size())
	    if (num[start[pi][i]]++ == 0)
		h_set.push(pint(uh[start[pi][i]], start[pi][i]));
	rep(i, end[pi].size())
	    --num[end[pi][i]];

	while (!h_set.empty() && num[h_set.top().second] == 0)
	    h_set.pop();

	if (!h_set.empty())
	{
	    ll max_h = h_set.top().first;
	    ll len = pos[pi + 1] - pos[pi];
	    area += len * max_h;
	}
    }
    printf("%lld\n", area);
}