比赛 |
20251001国庆欢乐赛1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
火柴排队 |
最终得分 |
100 |
用户昵称 |
zhyn |
运行时间 |
0.149 s |
代码语言 |
C++ |
内存使用 |
4.65 MiB |
提交时间 |
2025-10-01 09:59:58 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
int n;
struct node{
ll x;
int y;
};
node a[maxn],b[maxn];
ll ans=0;
int t[maxn];
int u[maxn],v[maxn],r[maxn],last[maxn];
bool cmp(node p,node q){
return p.x<q.x;
}
const ll mod=99999997;
void meg(int l,int r){
if(l==r){
return;
}
int mid=(l+r)/2;
meg(l,mid),meg(mid+1,r);
for(int i=l,j=mid+1,k=l;k<=r;k++){
if(i==mid+1){
t[k]=last[j++];
}
else if(j==r+1){
t[k]=last[i++];
}
else{
if(last[i]<=last[j]){
t[k]=last[i++];
}
else{
t[k]=last[j++];
ans+=mid-i+1;
ans%=mod;
}
}
}
for(int i=l;i<=r;i++){
last[i]=t[i];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("MatchNOIP2013.in","r",stdin);
freopen("MatchNOIP2013.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x;
a[i].y=i;
}
for(int i=1;i<=n;i++){
cin>>b[i].x;
b[i].y=i;
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++){
u[a[i].y]=i;
v[b[i].y]=i;
}
for(int i=1;i<=n;i++){
r[u[i]]=i;
}
for(int i=1;i<=n;i++){
last[i]=r[v[i]];
}
meg(1,n);
cout<<ans;
return 0;
}