记录编号 192949 评测结果 AAAAAAAAAA
题目名称 [NOIP 2013]火柴排队 最终得分 100
用户昵称 Gravatar/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();*/
}