比赛 |
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;
}