求改,连样例都没过
查看原帖
求改,连样例都没过
865793
better_Z楼主2023/7/26 18:30
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int mod=1e8-3;
int n;
long long ans=0,t[maxn],f[maxn];
struct crood{
    int h,n;
}a[maxn],b[maxn];
bool cmp(crood x,crood y){
    return x.h<y.h;
}
void merge_sort(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    merge_sort(l,mid),merge_sort(mid+1,r);
    for(int i=l,j=l,k=mid+1;i<=r;i++){
        if(j==mid+1)t[i]=f[k++];
        else if(k==r+1){t[i]=f[j++];(ans+=(k-mid-1))%mod;}
        else if(f[j]<=f[k]){t[i]=f[j++];(ans+=(k-mid-1))%mod;}
        else t[i]=f[k++];
    }
    for(int i=l;i<=r;i++)f[i]=t[i];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].h>>b[i].h;
        a[i].n=i,b[i].n=i;
    };
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        f[b[i].n]=a[i].n;
    }
    merge_sort(1,n);
    cout<<ans;
    return 0;
}
2023/7/26 18:30
加载中...