#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int mod = 1e9 + 7;
const int MAXN = 100005;
struct bit{
int tree[MAXN];
void add(int x, int v){
for(int i = x; i < MAXN; i += i & -i) tree[i] += v;
}
int query(int x){
int ret = 0;
for(int i = x; i; i -= i & -i) ret += tree[i];
return ret;
}
}bit;
vector<int> v[MAXN];
map<pi, lint> mp;
lint query(int x, int y){
if(sz(v[x]) > sz(v[y])) return -query(y, x);
if(mp.count(pi(x, y))) return mp[pi(x, y)];
lint ret = 0;
for(int i = 0; i < sz(v[x]); i++){
int p = lower_bound(all(v[y]), v[x][i]) - v[y].begin();
ret += sz(v[y]) - 2 * p;
}
return mp[pi(x, y)] = ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k, q; cin >> n >> k >> q;
vector<int> ord(k); iota(all(ord), 1);
vector<int> a(n);
lint ret = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
ret += bit.query(k) - bit.query(a[i]);
bit.add(a[i], 1);
v[a[i]].push_back(i);
}
while(q--){
int x; cin >> x;
int l = ord[x - 1], r = ord[x];
swap(ord[x - 1], ord[x]);
ret += query(l, r);
cout << ret << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2772 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
5 ms |
2772 KB |
Output is correct |
6 |
Correct |
4 ms |
2900 KB |
Output is correct |
7 |
Correct |
4 ms |
2900 KB |
Output is correct |
8 |
Correct |
5 ms |
3100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
3604 KB |
Output is correct |
2 |
Correct |
14 ms |
3736 KB |
Output is correct |
3 |
Correct |
13 ms |
3668 KB |
Output is correct |
4 |
Correct |
12 ms |
3640 KB |
Output is correct |
5 |
Correct |
15 ms |
3788 KB |
Output is correct |
6 |
Correct |
22 ms |
3912 KB |
Output is correct |
7 |
Correct |
26 ms |
4816 KB |
Output is correct |
8 |
Correct |
23 ms |
5776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
16456 KB |
Output is correct |
2 |
Correct |
182 ms |
17060 KB |
Output is correct |
3 |
Correct |
278 ms |
17436 KB |
Output is correct |
4 |
Correct |
484 ms |
18016 KB |
Output is correct |
5 |
Correct |
634 ms |
20556 KB |
Output is correct |
6 |
Correct |
647 ms |
20848 KB |
Output is correct |
7 |
Correct |
641 ms |
20752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2772 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
5 ms |
2772 KB |
Output is correct |
6 |
Correct |
4 ms |
2900 KB |
Output is correct |
7 |
Correct |
4 ms |
2900 KB |
Output is correct |
8 |
Correct |
5 ms |
3100 KB |
Output is correct |
9 |
Correct |
11 ms |
3604 KB |
Output is correct |
10 |
Correct |
14 ms |
3736 KB |
Output is correct |
11 |
Correct |
13 ms |
3668 KB |
Output is correct |
12 |
Correct |
12 ms |
3640 KB |
Output is correct |
13 |
Correct |
15 ms |
3788 KB |
Output is correct |
14 |
Correct |
22 ms |
3912 KB |
Output is correct |
15 |
Correct |
26 ms |
4816 KB |
Output is correct |
16 |
Correct |
23 ms |
5776 KB |
Output is correct |
17 |
Correct |
166 ms |
16456 KB |
Output is correct |
18 |
Correct |
182 ms |
17060 KB |
Output is correct |
19 |
Correct |
278 ms |
17436 KB |
Output is correct |
20 |
Correct |
484 ms |
18016 KB |
Output is correct |
21 |
Correct |
634 ms |
20556 KB |
Output is correct |
22 |
Correct |
647 ms |
20848 KB |
Output is correct |
23 |
Correct |
641 ms |
20752 KB |
Output is correct |
24 |
Correct |
599 ms |
22092 KB |
Output is correct |
25 |
Correct |
640 ms |
23876 KB |
Output is correct |
26 |
Correct |
780 ms |
27056 KB |
Output is correct |
27 |
Correct |
857 ms |
30148 KB |
Output is correct |
28 |
Correct |
926 ms |
34732 KB |
Output is correct |
29 |
Correct |
1051 ms |
43100 KB |
Output is correct |
30 |
Correct |
1163 ms |
51920 KB |
Output is correct |
31 |
Correct |
1166 ms |
51716 KB |
Output is correct |
32 |
Correct |
637 ms |
85644 KB |
Output is correct |
33 |
Correct |
843 ms |
21988 KB |
Output is correct |
34 |
Correct |
948 ms |
23688 KB |
Output is correct |
35 |
Correct |
1004 ms |
25680 KB |
Output is correct |
36 |
Correct |
1409 ms |
35600 KB |
Output is correct |
37 |
Correct |
2344 ms |
81572 KB |
Output is correct |
38 |
Correct |
2127 ms |
82628 KB |
Output is correct |
39 |
Correct |
1492 ms |
85828 KB |
Output is correct |
40 |
Correct |
1135 ms |
64392 KB |
Output is correct |
41 |
Correct |
1168 ms |
69880 KB |
Output is correct |
42 |
Correct |
987 ms |
85168 KB |
Output is correct |
43 |
Correct |
1066 ms |
84856 KB |
Output is correct |
44 |
Correct |
1222 ms |
85336 KB |
Output is correct |
45 |
Correct |
1130 ms |
85288 KB |
Output is correct |
46 |
Correct |
1300 ms |
65472 KB |
Output is correct |
47 |
Correct |
1491 ms |
72172 KB |
Output is correct |
48 |
Correct |
2684 ms |
84564 KB |
Output is correct |
49 |
Correct |
2535 ms |
84176 KB |
Output is correct |
50 |
Correct |
717 ms |
85352 KB |
Output is correct |
51 |
Correct |
667 ms |
84500 KB |
Output is correct |
52 |
Correct |
646 ms |
84184 KB |
Output is correct |
53 |
Correct |
806 ms |
85232 KB |
Output is correct |
54 |
Correct |
865 ms |
85176 KB |
Output is correct |
55 |
Correct |
2 ms |
2644 KB |
Output is correct |