90分,为什么第八个点错呢,离散化
查看原帖
90分,为什么第八个点错呢,离散化
488577
yh200314楼主2021/7/20 16:58
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e4 + 5;
int n;
ll li[maxn], ri[maxn], lsh[maxn], x[maxn], ans;
map<ll, bool> mp;
int main() {
    cin >> n;
    int p = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> li[i] >> ri[i];
        if (!mp[li[i]]) {
            lsh[++p] = li[i];
            mp[li[i]] = true;
        }
        if (!mp[ri[i]]) {
            lsh[++p] = ri[i];
            mp[ri[i]] = true;
        }
    }
    sort(lsh + 1, lsh + p + 1);
    for (int i = 1; i <= n; ++i){
        int a = lower_bound(lsh + 1, lsh + p + 1, li[i]) - lsh;
        int b = lower_bound(lsh + 1, lsh + p + 1, ri[i]) - lsh;
        for (int j = a + 1; j <= b; ++j) {
            if (!x[j]) {
                ans += lsh[j] - lsh[j - 1];
                x[j] = 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
2021/7/20 16:58
加载中...