比赛 20251001国庆欢乐赛1 评测结果 RRRRRRRRRR
题目名称 火柴排队 最终得分 0
用户昵称 二乾五 运行时间 1.426 s
代码语言 C++ 内存使用 3.34 MiB
提交时间 2025-10-01 10:49:04
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,b[1000005],t[1000005],ans;

struct matchs{
    ll a,b;
}a[1000005];

bool cmp(matchs x,matchs y){
    return x.a<y.a;
}

void GBsort(ll l,ll r){
    if(l>=r)return;
    ll mid=(l+r)>>1;
    GBsort(l,mid);
    GBsort(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(b[i]<=b[j]){
            t[k++]=b[i++];
        }else{
            t[k++]=b[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid){
        t[k++]=b[i++];
    }
    while(j<=r){
        t[k++]=b[j++];
    }
    foru(ii,l,r){
        b[ii]=t[ii];
    }
}

int main(){
    cin>>n;
    foru(i,1,n){
        cin>>a[i].a;
    }
    foru(i,1,n){
        cin>>a[i].b;
    }
    sort(a+1,a+n+1,cmp);
    foru(i,1,n){
        b[i]=a[i].b;
        cerr<<b[i]<<" ";
    }
    cerr<<endl;
    GBsort(1,n);
    foru(i,1,n){
        cerr<<b[i]<<" ";
    }
    cerr<<endl;
    cout<<ans;
    return 0;
}
//1 2 3 4
//1 3 2 4