#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, q, a[maxn], p[maxn];
vector<int> V[maxn];
namespace BIT {
int c[maxn];
void add(int p, int v) {
for (; p <= m; p += p & -p) c[p] += v;
}
int query(int p) {
int s = 0;
for (; p; p -= p & -p) s += c[p];
return s;
}
} // namespace BIT
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i], V[a[i]].push_back(i);
}
iota(p + 1, p + m + 1, 1);
long long ans = 0;
for (int i = n; i; i--) {
ans += BIT::query(a[i] - 1), BIT::add(a[i], 1);
}
auto solve = [&](int x, int y) {
static map<pair<int, int>, long long> mp;
if (mp.count({x, y})) return mp[{x, y}];
long long s = 0;
if (V[x].size() < V[y].size()) {
for (int i : V[x]) {
s += V[y].end() - lower_bound(V[y].begin(), V[y].end(), i);
}
} else {
for (int i : V[y]) {
s += lower_bound(V[x].begin(), V[x].end(), i) - V[x].begin();
}
}
return mp[{x, y}] = s;
};
while (q--) {
int k;
cin >> k;
ans += solve(p[k], p[k + 1]);
swap(p[k], p[k + 1]), ans -= solve(p[k], p[k + 1]);
cout << ans << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
3 ms |
2792 KB |
Output is correct |
3 |
Correct |
3 ms |
2736 KB |
Output is correct |
4 |
Correct |
8 ms |
2776 KB |
Output is correct |
5 |
Correct |
6 ms |
2900 KB |
Output is correct |
6 |
Correct |
6 ms |
2952 KB |
Output is correct |
7 |
Correct |
6 ms |
3028 KB |
Output is correct |
8 |
Correct |
6 ms |
3284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
3600 KB |
Output is correct |
2 |
Correct |
16 ms |
3992 KB |
Output is correct |
3 |
Correct |
14 ms |
3968 KB |
Output is correct |
4 |
Correct |
11 ms |
4052 KB |
Output is correct |
5 |
Correct |
15 ms |
4232 KB |
Output is correct |
6 |
Correct |
18 ms |
4408 KB |
Output is correct |
7 |
Correct |
18 ms |
5328 KB |
Output is correct |
8 |
Correct |
19 ms |
6412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
171 ms |
16632 KB |
Output is correct |
2 |
Correct |
194 ms |
16840 KB |
Output is correct |
3 |
Correct |
428 ms |
17420 KB |
Output is correct |
4 |
Correct |
856 ms |
18400 KB |
Output is correct |
5 |
Correct |
1179 ms |
22312 KB |
Output is correct |
6 |
Correct |
1153 ms |
23052 KB |
Output is correct |
7 |
Correct |
1107 ms |
22612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
3 ms |
2792 KB |
Output is correct |
3 |
Correct |
3 ms |
2736 KB |
Output is correct |
4 |
Correct |
8 ms |
2776 KB |
Output is correct |
5 |
Correct |
6 ms |
2900 KB |
Output is correct |
6 |
Correct |
6 ms |
2952 KB |
Output is correct |
7 |
Correct |
6 ms |
3028 KB |
Output is correct |
8 |
Correct |
6 ms |
3284 KB |
Output is correct |
9 |
Correct |
11 ms |
3600 KB |
Output is correct |
10 |
Correct |
16 ms |
3992 KB |
Output is correct |
11 |
Correct |
14 ms |
3968 KB |
Output is correct |
12 |
Correct |
11 ms |
4052 KB |
Output is correct |
13 |
Correct |
15 ms |
4232 KB |
Output is correct |
14 |
Correct |
18 ms |
4408 KB |
Output is correct |
15 |
Correct |
18 ms |
5328 KB |
Output is correct |
16 |
Correct |
19 ms |
6412 KB |
Output is correct |
17 |
Correct |
171 ms |
16632 KB |
Output is correct |
18 |
Correct |
194 ms |
16840 KB |
Output is correct |
19 |
Correct |
428 ms |
17420 KB |
Output is correct |
20 |
Correct |
856 ms |
18400 KB |
Output is correct |
21 |
Correct |
1179 ms |
22312 KB |
Output is correct |
22 |
Correct |
1153 ms |
23052 KB |
Output is correct |
23 |
Correct |
1107 ms |
22612 KB |
Output is correct |
24 |
Correct |
1119 ms |
25076 KB |
Output is correct |
25 |
Correct |
1127 ms |
28076 KB |
Output is correct |
26 |
Correct |
1225 ms |
33112 KB |
Output is correct |
27 |
Correct |
1366 ms |
38556 KB |
Output is correct |
28 |
Correct |
1601 ms |
45932 KB |
Output is correct |
29 |
Correct |
1792 ms |
58548 KB |
Output is correct |
30 |
Correct |
1881 ms |
71020 KB |
Output is correct |
31 |
Correct |
1882 ms |
70812 KB |
Output is correct |
32 |
Correct |
1300 ms |
148212 KB |
Output is correct |
33 |
Correct |
1655 ms |
25268 KB |
Output is correct |
34 |
Correct |
1924 ms |
28464 KB |
Output is correct |
35 |
Correct |
2142 ms |
32176 KB |
Output is correct |
36 |
Correct |
3024 ms |
52004 KB |
Output is correct |
37 |
Execution timed out |
5090 ms |
143164 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |