比赛 20251001国庆欢乐赛1 评测结果 AAAAAAAAAA
题目名称 火柴排队 最终得分 100
用户昵称 对立猫猫对立 运行时间 0.169 s
代码语言 C++ 内存使用 4.73 MiB
提交时间 2025-10-01 11:05:54
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
#define fora(i, a, b, c) for(int i = a; i <= b; i += c)
#define forb(i, a, b, c) for(int i = a; i >= b; i -= c)
#define lowbit(x) (x & (-x))
#define N 100005
#define MOD 99999997
using namespace std;
struct Node {
	int idx, dat, goal;
	bool operator<(Node a) {return dat < a.dat;}
};
Node a[N], b[N];
int n, f[N], cnt;
void add(int x, int y) {
	for (; x <= n; x += lowbit(x)) f[x] += y;
}
int ask(int x) {
	int ans = 0;
	for (; x; x -= lowbit(x)) ans += f[x];
	return ans;
}
bool cmp(Node a, Node b) {
	return a.idx < b.idx;
}
signed main() {
	freopen("MatchNOIP2013.in", "r", stdin);
	freopen("MatchNOIP2013.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	fora(i, 1, n, 1) {
		cin >> a[i].dat;
		a[i].idx = i;
	}
	fora(i, 1, n, 1) {
		cin >> b[i].dat;
		b[i].idx = i;
	}
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	fora(i, 1, n, 1) {
		b[i].goal = a[i].idx;
	}
	sort(b + 1, b + n + 1, cmp);
	forb(i, n, 1, 1) {
		cnt += ask(b[i].goal - 1);
		add(b[i].goal, 1);
	}
	cout << cnt % MOD << endl;
	return 0;
}