比赛 |
20251001国庆欢乐赛1 |
评测结果 |
C |
题目名称 |
火柴排队 |
最终得分 |
0 |
用户昵称 |
wdsjl |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2025-10-01 10:27:28 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010;
const int mod = 99999997;
struct node{
int v,idx;
}a[N],b[N],c[N];
bool cmp(node a,node b){
return a.v<b.v;
}
bool cmp1(node a,node b){
if(a.v==b.v)return a.idx>b.idx;
return a.v>b.v;
}
int sum[N];
int n,res;
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))sum[i]+=v;
}
int query(int x){
int cnt=0;
for(int i=x;i;i-=lowbit(i))cnt+=sum[i];
return cnt;
}
signed main(){
freopen("MatchNOIP2013.in"."r",stdin);
freopen("MatchNOIP2013.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].v);
a[i].idx=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
scanf("%lld",&b[i].v);
b[i].idx=i;
}
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++){
c[b[i].idx].v=a[i].idx;
c[i].idx=i;
}
sort(c+1,c+1+n,cmp1);
for(int i=1;i<=n;i++){
res=(res+query(c[i].idx)%mod)%mod;
// res+=query(c[i].idx);
add(c[i].idx,1);
}
printf("%lld",res);
return 0;
}