Submission #71489617

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(arg) cout << "[" << #arg << "]: " << arg << endl
#else
#define debug(arg) 42
#endif

using llu = uint64_t;
using ll = int64_t;

#define vec vector
#define pb push_back
#define all(n) begin(n), end(n)

void solv() {
	int n, q; cin >> n >> q;
	map<int, int> ranges;
	int ans = 0;
	while (q--) {
		int l, r; cin >> l >> r;
		auto it = ranges.lower_bound(l);
		while (it != ranges.end() && it->first <= r) {
			r = max(r, it->second);
			ans -= it->second - it->first + 1;
			it = ranges.erase(it);
		}
		if (it != ranges.begin()) {
			--it;
			if (it->second >= l) {
				l = min(l, it->first);
				r = max(r, it->second);
				ans -= it->second - it->first + 1;
				it = ranges.erase(it);
			}
		}
		ranges[l] = r;
		ans += r - l + 1;
		cout << n - ans << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solv();
	return 0;
}

Submission Info

Judge Result