#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll fen[200005];
int n;
void update(int id, int val) {
id++;
while(id <= n + 1) {
fen[id] += val;
id += (id & (-id));
}
return;
}
ll pre(int id) {
if(id <= -1) return 0;
int ans = 0;
id++;
while(id) {
ans += fen[id];
id -= (id & (-id));
}
return ans;
}
int range(int l, int r){
return pre(r) - pre(l - 1);
}
long long count_swaps(vector<int> arr) {
n = arr.size();
queue<int> pl[n + 5];
int dk[n + 5];
int t = 0;
for(int i = 0; i < n; i++) {
if(arr[i] < 0) {
dk[i] = t;
t++;
pl[-arr[i]].push(t);
t++;
}
}
for(int i = 0; i < n; i++) {
if(arr[i] > 0) {
dk[i] = pl[arr[i]].front();
pl[arr[i]].pop();
}
}
ll ans = 0;
for(int i = 0; i < n; i++) {
ans += i - pre(dk[i]);
update(dk[i], 1);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
288 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
304 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
1612 KB |
Output is correct |
19 |
Correct |
2 ms |
1612 KB |
Output is correct |
20 |
Correct |
12 ms |
14288 KB |
Output is correct |
21 |
Correct |
14 ms |
14284 KB |
Output is correct |
22 |
Correct |
128 ms |
139468 KB |
Output is correct |
23 |
Correct |
131 ms |
140460 KB |
Output is correct |
24 |
Correct |
131 ms |
140532 KB |
Output is correct |
25 |
Correct |
148 ms |
140296 KB |
Output is correct |
26 |
Correct |
129 ms |
140532 KB |
Output is correct |
27 |
Correct |
129 ms |
140236 KB |
Output is correct |
28 |
Correct |
130 ms |
140548 KB |
Output is correct |
29 |
Correct |
128 ms |
140604 KB |
Output is correct |
30 |
Correct |
130 ms |
140424 KB |
Output is correct |
31 |
Correct |
130 ms |
140460 KB |
Output is correct |
32 |
Correct |
137 ms |
140524 KB |
Output is correct |
33 |
Correct |
126 ms |
140204 KB |
Output is correct |
34 |
Correct |
124 ms |
140448 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
1 ms |
204 KB |
Output is correct |
37 |
Correct |
124 ms |
140460 KB |
Output is correct |
38 |
Correct |
126 ms |
140412 KB |
Output is correct |
39 |
Correct |
141 ms |
140500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
284 KB |
Output is correct |
5 |
Correct |
142 ms |
138836 KB |
Output is correct |
6 |
Correct |
136 ms |
139972 KB |
Output is correct |
7 |
Correct |
142 ms |
140076 KB |
Output is correct |
8 |
Correct |
127 ms |
140480 KB |
Output is correct |
9 |
Correct |
139 ms |
140076 KB |
Output is correct |
10 |
Correct |
143 ms |
140080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
288 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
288 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |