Submission #71576636

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define memo(v, x) memset(v, x, sizeof(v))
#define sz(v) (int)v.size()


void solve() {
    int n, q;
    cin >> n >> q;
    int black = 0;
    set<pair<int, int>> v;
    auto extend = [&](int l, int r) -> void {
		auto it = v.lower_bound({l, -1});
		vector<pair<int, int>> add, remove;
		add.push_back({l, r});
		if (it != v.begin()) {
			it--;
			if ((*it).second >= l) {
				add.push_back({(*it).first, l - 1});
				if ((*it).second > r)
					add.push_back({r + 1, (*it).second});
				remove.push_back(*it);
			}
			it++;
		}
		while (it != v.end() && (*it).second <= r) {
			auto [inL, inR] = (*it);
			remove.push_back({inL, inR});
			it++;
		}
		if (it != v.end() && (*it).first <= r) {
			auto [inL, inR] = *it;
			inR = min(inR, r);
			if (r + 1 <= (*it).second)
				add.push_back({r + 1, (*it).second});
			remove.push_back(*it);
		}
		for (auto &seg : remove) {
            black -= (seg.second - seg.first + 1);
            v.erase(seg);
        }
		for (auto &seg : add) {
            black += (seg.second - seg.first + 1);
            v.insert(seg);
        }
	};
    while (q--) {
        int l, r;
        cin >> l >> r;
        extend(l, r);
        cout << n - black << '\n';
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result