离散化救助,照着深进上写的
查看原帖
离散化救助,照着深进上写的
779997
like_tis楼主2023/11/10 21:42
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,l[20005],r[20005],b[20005],c[20005],tb,tc;
bool f[200005];
ll ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
        b[++tb]=l[i];
        b[++tb]=r[i];
    }
    sort(b+1,b+tb+1);
    for(int i=1;i<=tb;i++){
        if(b[i]!=b[i-1]||i==1){
            c[++tc]=b[i];
        }
    }
    for(int i=1;i<=n;i++){
        int x=lower_bound(c+1,c+tc+1,l[i])-c;
        int y=lower_bound(c+1,c+tc+1,r[i])-c;
        for(int j=x;j<y;j++){
            f[j]=true;
        }
    }
    for(int i=1;i<=tc;i++){
        if(f[i]==true) ans+=c[i+1]-c[i];
    }
    printf("%lld",ans);
    return 0;
}
2023/11/10 21:42
加载中...