记录编号 |
192949 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2013]火柴排队 |
最终得分 |
100 |
用户昵称 |
/k |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.142 s |
提交时间 |
2015-10-13 15:50:33 |
内存使用 |
3.75 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
struct u
{
int z;
int d;
int x;
}a[100010],b[100010];
int w[100010],q[100010];
int c[100010];
long long r;
inline int gl(int a)
{
return a&(-a);
}
inline void gj(int a)
{
while(a<=n)
{
c[a]++;
a+=gl(a);
}
}
inline int gs(int a)
{
int uu=0;
while(a>0)
{
uu+=c[a];
a-=gl(a);
}
return uu;
}
inline bool g(const u & aa,const u & bb)
{
return aa.z<bb.z;
}
int main()
{
freopen("MatchNOIP2013.in","r",stdin);
freopen("MatchNOIP2013.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].z);
a[i].d=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i].z);
b[i].d=i;
}
sort(b+1,b+1+n,g);
for(int i=1;i<=n;i++)
w[i]=b[i].d;
sort(a+1,a+1+n,g);
for(int i=1;i<=n;i++)
q[a[i].d]=w[i];
for(int i=1;i<=n;i++)
{
gj(q[i]);
r+=i-gs(q[i]);
}
r%=99999997;
printf("%lld",r);
/* getchar();
getchar();*/
}