求助离散化WA on #8 90pts
  • 板块P1496 火烧赤壁
  • 楼主monodev
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/11 17:00
  • 上次更新2023/11/11 19:05:37
查看原帖
求助离散化WA on #8 90pts
533102
monodev楼主2023/11/11 17:00
#include <iostream>
#include <algorithm>
using namespace std;

int sorted[40001], setkind[40001];
int sortedtop,     setkindtop;

int a[20001], b[20001];

bool onfire[20001];

int main(){
	sortedtop = setkindtop = -1;
	
	int n;
	cin >> n;
	for(int i = 0; i < n; ++ i){
		cin >> a[i] >> b[i];
		sorted[++ sortedtop] = a[i];
		sorted[++ sortedtop] = b[i];
	}
	sort(sorted, sorted + sortedtop);
	for(int i = 0; i < sortedtop; ++ i)
		if(i == 0 || sorted[i] != sorted[i - 1])
			setkind[++ setkindtop] = sorted[i];
	
	for(int i = 0; i < n; ++ i){
		int apos = lower_bound(setkind, setkind + setkindtop, a[i]) - setkind;
		int bpos = lower_bound(setkind, setkind + setkindtop, b[i]) - setkind;
		for(int j = apos; j < bpos; ++ j)
			onfire[j] = true;
	}
	
	int ans = 0;
	for(int i = 0; i < setkindtop; ++ i)
		if(onfire[i])
			ans += setkind[i + 1] - setkind[i];
	
	cout << ans << endl;
}
2023/11/11 17:00
加载中...