区间合并的写法为什么只能过两个?怎么写噢
查看原帖
区间合并的写法为什么只能过两个?怎么写噢
1073916
Kurumi113楼主2024/8/22 10:38
#include <bits/stdc++.h>
#define all(_) _.begin(),_.end()
#define pb push_back
#define eb emplace_back
#define debug(x) std::cerr << #x << " = " << x << "\n"
#define ma(type, name, _x, _y) std::vector<std::vector<type>> name(_x + 10, std::vector<type>(_y + 10, 0))
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using db = long double;
using PII = std::pair<int, int>;
std::mt19937 mrand( std::random_device{}() );
int salt(int dom) { return mrand() % dom + 1; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(20);
	
	int l, m;
	std::cin >> l >> m;
	std::set<PII> p;
	std::vector<PII> ans; 
	while(m--) {
		int u, v;
		std::cin >> u >> v;
		p.insert({u, v});
	}
	int st = -2e9, ed = -2e9;
	for(auto [x, y] : p) {
		if(ed < x) {
			if(st != -2e9) {
				ans.pb({st, ed});
			}
			st = x, ed = y;
		} else {
			ed = y;
		}
	}
	if(st != -2e9) ans.pb({st, ed});
	int cnt = 0, res = 0;
	int rank = 0;
	for(auto [x, y] : ans) {
	
		//std::cout << x << " " << y << "\n";
		cnt += y - x + 1;
	}
	res = l - cnt + 1;
	std::cout << res << "\n";
    return 0;
}


2024/8/22 10:38
加载中...