P2061 [USACO07OPEN] City Horizon S

应该是最短的了, $51$ 行, 除了堆，没有树形结构.

但感觉写得还是有些臃肿.

不是想拿最短解, 而是其他扫描线题没法这么写，这么一坨屎太难调了.

#include<cstdio>
#include<algorithm>
#include<utility>
#include<unordered_map>
#include<queue>
using namespace std;

#define Q 40005
#define int long long

int q;
pair<int,pair<int,int> > queries[Q<<1];
priority_queue<int> bds;
unordered_map<int,int> del;

signed main()
{
	scanf("%lld",&q);
	for(int i=1;i<=q;++i)
	{
		int l,r,h;
		scanf("%lld%lld%lld",&l,&r,&h);--r;
		queries[i-1<<1|1]=make_pair(0,make_pair(l,h));
		queries[i<<1]=make_pair(1,make_pair(r,h));
	}
	sort(queries+1,queries+(q<<1|1),[](pair<int,pair<int,int> > a,pair<int,pair<int,int> > b){return a.second.first<b.second.first;});
	int last=queries[1].second.first,ans=0;
	bds.push(0);
	for(int i=1;i<=q<<1;++i)
	{
		if(i>1&&queries[i].second.first>queries[i-1].second.first)
		{
			ans+=bds.top()*(queries[i].second.first-last);
			while(del[bds.top()])
				--del[bds.top()],bds.pop();
		}
		if(queries[i].first)
			++del[queries[i].second.second];
		else
			bds.push(queries[i].second.second);
		if(i==(q<<1)||queries[i].second.first<queries[i+1].second.first)
		{
			ans+=bds.top();
			last=queries[i].second.first+1;
			while(del[bds.top()])
				--del[bds.top()],bds.pop();
		}
	}
	printf("%lld",ans);
	return 0;
}