比赛 20251001国庆欢乐赛1 评测结果 WWWWWWWWWW
题目名称 火柴排队 最终得分 0
用户昵称 会挽弯弓满月 运行时间 0.189 s
代码语言 C++ 内存使用 4.62 MiB
提交时间 2025-10-01 11:13:04
显示代码纯文本
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10,mod=99999997;
ll n,ans;
ll a[N],b[N];
ll ar[N],br[N];
ll id[N];
bool vis[N];
int main(){
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",ar+i);
        a[i]=ar[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",br+i);
        b[i]=br[i];
    }
    ll l1,l2;
    sort(ar+1,ar+n+1);
    sort(br+1,br+n+1);
    l1=unique(ar+1,ar+n+1)-ar-1;
    l2=unique(br+1,br+n+1)-br-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(ar+1,ar+l1+1,a[i])-ar;
        b[i]=lower_bound(br+1,br+l2+1,b[i])-br;
        id[b[i]]=i;
    }
    /*
    for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    cout<<endl;
    for(int i=1;i<=n;i++) printf("%lld ",b[i]);
    cout<<endl;
    */
    ll cnt=1,t;
    for(ll i=1;i<=n;i++){
        //printf("i=%d cnt=%d\n",i,cnt);
        if(a[i]==b[cnt]){
            //printf("same\n");
            cnt++;
            while(vis[cnt]==1) cnt++;
            //cout<<endl;
            continue; 
        }
        //printf("not same\n");
        t=id[a[i]];
        //printf("b[%d]=%d t=%d\n",cnt,b[cnt],t);
        t-=cnt;
        ans=(ans+t)%mod;
        vis[id[a[i]]]=1;
        //cout<<endl;
    }
    printf("%lld",ans);
    return 0;
}