火烧赤壁

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const long long INF = 1e17; //❄️
    5int main() {
    6    ios::sync_with_stdio(0); cin.tie(0); 
    7    int n; cin >> n;
    8    vector<ll> a;
    9    vector<pair<ll, ll>> v;
    10    for (int i = 0; i < n; i++) {
    11        ll x, y; cin >> x >> y;
    12        a.push_back(x); a.push_back(y);
    13        v.emplace_back(x, y);
    14    }
    15    sort(a.begin(), a.end());
    16    a.erase(unique(a.begin(), a.end()), a.end());
    17    auto get_id = [&] (ll x) {
    18        return lower_bound(a.begin(), a.end(), x) - a.begin();
    19    };
    20    vector<bool> vis(a.size() - 1);
    21    //or use differene array to optimize
    22    for (int i = 0; i < v.size(); i++) {
    23        auto[x, y] = v[i];
    24        x = get_id(x); y = get_id(y);
    25        //[x, y)
    26        for (int j = x; j < y; j++) {
    27            vis[j] = 1;
    28        }
    29    }
    30    ll ans = 0;
    31    for (int i = 0; i < vis.size(); i++) {
    32        if (vis[i]) ans += a[i + 1] - a[i];
    33    }
    34    cout << ans << '\n';
    35    return 0;
    36}