比赛 |
20251001国庆欢乐赛1 |
评测结果 |
AAAAAAAAWW |
题目名称 |
火柴排队 |
最终得分 |
80 |
用户昵称 |
秋_Water |
运行时间 |
0.251 s |
代码语言 |
C++ |
内存使用 |
4.61 MiB |
提交时间 |
2025-10-01 11:10:58 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int N=1e6+7;
int n,t[N],c[N];
struct node{
int val,id;
}a[N],b[N];
bool cmp(node x,node y){
return x.val<y.val;
}
void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
t[i]+=val;
}
}
int query(int x){
int ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=t[i];
}
return ans;
}
signed main(){
freopen("MatchNOIP2013.in","r",stdin);
freopen("MatchNOIP2013.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].id=i;
}
for(int i=1;i<=n;i++){
cin>>b[i].val;
b[i].id=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++){
c[b[i].id]=a[i].id;
}
int ans=0;
for(int i=n;i;i--){
ans+=query(c[i]);
add(c[i],1);
}
cout<<ans;
return 0;
}