#include <bits/stdc++.h>
#include "shoes.h"
#define f first
#define s second
using namespace std;
const int maxn = 2e5 + 69;
set<int> l[maxn], r[maxn];
vector<int> f(maxn);
vector<int> pr(maxn);
void add(int v, int x) {
for(int i = v;i < maxn;i += (i & -i))
f[i] += x;
}
int qry(int v) {
int res = 0;
for(int i = v;i >= 1;i -= (i & -i))
res += f[i];
return res;
}
long long count_swaps(vector<int> s) {
int n = s.size();
vector<int> a(n + 1);
for(int i = 0;i < n;i++) {
a[i + 1] = s[i];
}
vector<int> vis(n + 1);
vector<pair<int, int>> par;
for(int i = 1;i <= n;i++) {
if(a[i] < 0)
l[abs(a[i])].insert(i);
else
r[a[i]].insert(i);
}
for(int i = 1;i <= n;i++) {
if(a[i] < 0 && !vis[i]) {
auto u = *r[abs(a[i])].upper_bound(i);
r[abs(a[i])].erase(u);
par.push_back({i, u});
vis[i] = vis[u] = 1;
}
else if(a[i] > 0 && !vis[i]) {
auto u = *l[a[i]].upper_bound(i);
l[a[i]].erase(u);
par.push_back({i, u});
vis[i] = vis[u] = 1;
}
}
long long ans = 0;
for(auto x : par) {
int levi = x.f + qry(x.f);
int desni = x.s + qry(x.s);
if(a[x.f] < 0)
ans += (desni - levi - 1);
else
ans += (desni - levi);
add(x.f + 1, 1);
add(x.s, -1);
}
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int tt = 1;
// //cin >> tt;
// while(tt--) {
// int n;
// cin >> n;
// vector<int> a(2 * n);
// for(int i = 0;i < 2 * n;i++)
// cin >> a[i];
// cout << count_swaps(a) << endl;
// }
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20672 KB |
Output is correct |
3 |
Correct |
8 ms |
20564 KB |
Output is correct |
4 |
Correct |
8 ms |
20564 KB |
Output is correct |
5 |
Correct |
9 ms |
20564 KB |
Output is correct |
6 |
Correct |
8 ms |
20564 KB |
Output is correct |
7 |
Correct |
9 ms |
20564 KB |
Output is correct |
8 |
Correct |
9 ms |
20564 KB |
Output is correct |
9 |
Correct |
8 ms |
20564 KB |
Output is correct |
10 |
Correct |
10 ms |
20564 KB |
Output is correct |
11 |
Correct |
9 ms |
20640 KB |
Output is correct |
12 |
Correct |
9 ms |
20612 KB |
Output is correct |
13 |
Correct |
9 ms |
20676 KB |
Output is correct |
14 |
Correct |
9 ms |
20668 KB |
Output is correct |
15 |
Correct |
9 ms |
20564 KB |
Output is correct |
16 |
Correct |
9 ms |
20564 KB |
Output is correct |
17 |
Correct |
9 ms |
20564 KB |
Output is correct |
18 |
Correct |
9 ms |
20564 KB |
Output is correct |
19 |
Correct |
9 ms |
20576 KB |
Output is correct |
20 |
Correct |
9 ms |
20644 KB |
Output is correct |
21 |
Correct |
9 ms |
20552 KB |
Output is correct |
22 |
Correct |
9 ms |
20564 KB |
Output is correct |
23 |
Correct |
11 ms |
20564 KB |
Output is correct |
24 |
Correct |
9 ms |
20612 KB |
Output is correct |
25 |
Correct |
9 ms |
20552 KB |
Output is correct |
26 |
Correct |
9 ms |
20564 KB |
Output is correct |
27 |
Correct |
9 ms |
20564 KB |
Output is correct |
28 |
Correct |
9 ms |
20564 KB |
Output is correct |
29 |
Correct |
10 ms |
20564 KB |
Output is correct |
30 |
Correct |
8 ms |
20564 KB |
Output is correct |
31 |
Correct |
9 ms |
20564 KB |
Output is correct |
32 |
Correct |
9 ms |
20592 KB |
Output is correct |
33 |
Correct |
9 ms |
20564 KB |
Output is correct |
34 |
Correct |
9 ms |
20564 KB |
Output is correct |
35 |
Correct |
9 ms |
20672 KB |
Output is correct |
36 |
Correct |
9 ms |
20564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20672 KB |
Output is correct |
3 |
Correct |
9 ms |
20564 KB |
Output is correct |
4 |
Correct |
9 ms |
20564 KB |
Output is correct |
5 |
Correct |
9 ms |
20564 KB |
Output is correct |
6 |
Correct |
9 ms |
20564 KB |
Output is correct |
7 |
Correct |
8 ms |
20564 KB |
Output is correct |
8 |
Correct |
9 ms |
20616 KB |
Output is correct |
9 |
Correct |
9 ms |
20644 KB |
Output is correct |
10 |
Correct |
9 ms |
20564 KB |
Output is correct |
11 |
Correct |
9 ms |
20592 KB |
Output is correct |
12 |
Correct |
9 ms |
20632 KB |
Output is correct |
13 |
Correct |
9 ms |
20564 KB |
Output is correct |
14 |
Correct |
9 ms |
20564 KB |
Output is correct |
15 |
Correct |
9 ms |
20564 KB |
Output is correct |
16 |
Correct |
8 ms |
20564 KB |
Output is correct |
17 |
Correct |
9 ms |
20692 KB |
Output is correct |
18 |
Correct |
10 ms |
20692 KB |
Output is correct |
19 |
Correct |
9 ms |
20692 KB |
Output is correct |
20 |
Correct |
15 ms |
22100 KB |
Output is correct |
21 |
Correct |
14 ms |
22036 KB |
Output is correct |
22 |
Correct |
66 ms |
34324 KB |
Output is correct |
23 |
Correct |
78 ms |
34320 KB |
Output is correct |
24 |
Correct |
69 ms |
34252 KB |
Output is correct |
25 |
Correct |
65 ms |
33180 KB |
Output is correct |
26 |
Correct |
63 ms |
34240 KB |
Output is correct |
27 |
Correct |
67 ms |
34248 KB |
Output is correct |
28 |
Correct |
64 ms |
33096 KB |
Output is correct |
29 |
Correct |
65 ms |
33092 KB |
Output is correct |
30 |
Correct |
65 ms |
33088 KB |
Output is correct |
31 |
Correct |
65 ms |
34348 KB |
Output is correct |
32 |
Correct |
67 ms |
33168 KB |
Output is correct |
33 |
Correct |
65 ms |
33080 KB |
Output is correct |
34 |
Correct |
65 ms |
33112 KB |
Output is correct |
35 |
Correct |
10 ms |
20564 KB |
Output is correct |
36 |
Correct |
9 ms |
20564 KB |
Output is correct |
37 |
Correct |
68 ms |
33100 KB |
Output is correct |
38 |
Correct |
67 ms |
33100 KB |
Output is correct |
39 |
Correct |
65 ms |
33184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
20564 KB |
Output is correct |
2 |
Correct |
8 ms |
20564 KB |
Output is correct |
3 |
Correct |
9 ms |
20620 KB |
Output is correct |
4 |
Correct |
9 ms |
20564 KB |
Output is correct |
5 |
Correct |
53 ms |
33164 KB |
Output is correct |
6 |
Correct |
70 ms |
33176 KB |
Output is correct |
7 |
Correct |
53 ms |
33104 KB |
Output is correct |
8 |
Correct |
62 ms |
33064 KB |
Output is correct |
9 |
Correct |
53 ms |
33188 KB |
Output is correct |
10 |
Correct |
60 ms |
33076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20672 KB |
Output is correct |
3 |
Correct |
8 ms |
20564 KB |
Output is correct |
4 |
Correct |
8 ms |
20564 KB |
Output is correct |
5 |
Correct |
9 ms |
20564 KB |
Output is correct |
6 |
Correct |
8 ms |
20564 KB |
Output is correct |
7 |
Correct |
9 ms |
20564 KB |
Output is correct |
8 |
Correct |
9 ms |
20564 KB |
Output is correct |
9 |
Correct |
8 ms |
20564 KB |
Output is correct |
10 |
Correct |
10 ms |
20564 KB |
Output is correct |
11 |
Correct |
9 ms |
20640 KB |
Output is correct |
12 |
Correct |
9 ms |
20612 KB |
Output is correct |
13 |
Correct |
9 ms |
20676 KB |
Output is correct |
14 |
Correct |
9 ms |
20668 KB |
Output is correct |
15 |
Correct |
9 ms |
20564 KB |
Output is correct |
16 |
Correct |
9 ms |
20564 KB |
Output is correct |
17 |
Correct |
9 ms |
20564 KB |
Output is correct |
18 |
Correct |
9 ms |
20564 KB |
Output is correct |
19 |
Correct |
9 ms |
20576 KB |
Output is correct |
20 |
Correct |
9 ms |
20644 KB |
Output is correct |
21 |
Correct |
9 ms |
20552 KB |
Output is correct |
22 |
Correct |
9 ms |
20564 KB |
Output is correct |
23 |
Correct |
11 ms |
20564 KB |
Output is correct |
24 |
Correct |
9 ms |
20612 KB |
Output is correct |
25 |
Correct |
9 ms |
20552 KB |
Output is correct |
26 |
Correct |
9 ms |
20564 KB |
Output is correct |
27 |
Correct |
9 ms |
20564 KB |
Output is correct |
28 |
Correct |
9 ms |
20564 KB |
Output is correct |
29 |
Correct |
10 ms |
20564 KB |
Output is correct |
30 |
Correct |
8 ms |
20564 KB |
Output is correct |
31 |
Correct |
9 ms |
20564 KB |
Output is correct |
32 |
Correct |
9 ms |
20592 KB |
Output is correct |
33 |
Correct |
9 ms |
20564 KB |
Output is correct |
34 |
Correct |
9 ms |
20564 KB |
Output is correct |
35 |
Correct |
9 ms |
20672 KB |
Output is correct |
36 |
Correct |
9 ms |
20564 KB |
Output is correct |
37 |
Correct |
8 ms |
20564 KB |
Output is correct |
38 |
Correct |
9 ms |
20560 KB |
Output is correct |
39 |
Correct |
9 ms |
20564 KB |
Output is correct |
40 |
Correct |
9 ms |
20692 KB |
Output is correct |
41 |
Correct |
9 ms |
20692 KB |
Output is correct |
42 |
Correct |
9 ms |
20684 KB |
Output is correct |
43 |
Correct |
10 ms |
20808 KB |
Output is correct |
44 |
Correct |
10 ms |
20732 KB |
Output is correct |
45 |
Correct |
9 ms |
20804 KB |
Output is correct |
46 |
Correct |
9 ms |
20704 KB |
Output is correct |
47 |
Correct |
11 ms |
20736 KB |
Output is correct |
48 |
Correct |
9 ms |
20692 KB |
Output is correct |
49 |
Correct |
9 ms |
20692 KB |
Output is correct |
50 |
Correct |
9 ms |
20716 KB |
Output is correct |
51 |
Correct |
10 ms |
20692 KB |
Output is correct |
52 |
Correct |
9 ms |
20800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20672 KB |
Output is correct |
3 |
Correct |
8 ms |
20564 KB |
Output is correct |
4 |
Correct |
8 ms |
20564 KB |
Output is correct |
5 |
Correct |
9 ms |
20564 KB |
Output is correct |
6 |
Correct |
8 ms |
20564 KB |
Output is correct |
7 |
Correct |
9 ms |
20564 KB |
Output is correct |
8 |
Correct |
9 ms |
20564 KB |
Output is correct |
9 |
Correct |
8 ms |
20564 KB |
Output is correct |
10 |
Correct |
10 ms |
20564 KB |
Output is correct |
11 |
Correct |
9 ms |
20640 KB |
Output is correct |
12 |
Correct |
9 ms |
20612 KB |
Output is correct |
13 |
Correct |
9 ms |
20676 KB |
Output is correct |
14 |
Correct |
9 ms |
20668 KB |
Output is correct |
15 |
Correct |
9 ms |
20564 KB |
Output is correct |
16 |
Correct |
9 ms |
20564 KB |
Output is correct |
17 |
Correct |
9 ms |
20564 KB |
Output is correct |
18 |
Correct |
9 ms |
20564 KB |
Output is correct |
19 |
Correct |
9 ms |
20576 KB |
Output is correct |
20 |
Correct |
9 ms |
20644 KB |
Output is correct |
21 |
Correct |
9 ms |
20552 KB |
Output is correct |
22 |
Correct |
9 ms |
20564 KB |
Output is correct |
23 |
Correct |
11 ms |
20564 KB |
Output is correct |
24 |
Correct |
9 ms |
20612 KB |
Output is correct |
25 |
Correct |
9 ms |
20552 KB |
Output is correct |
26 |
Correct |
9 ms |
20564 KB |
Output is correct |
27 |
Correct |
9 ms |
20564 KB |
Output is correct |
28 |
Correct |
9 ms |
20564 KB |
Output is correct |
29 |
Correct |
10 ms |
20564 KB |
Output is correct |
30 |
Correct |
8 ms |
20564 KB |
Output is correct |
31 |
Correct |
9 ms |
20564 KB |
Output is correct |
32 |
Correct |
9 ms |
20592 KB |
Output is correct |
33 |
Correct |
9 ms |
20564 KB |
Output is correct |
34 |
Correct |
9 ms |
20564 KB |
Output is correct |
35 |
Correct |
9 ms |
20672 KB |
Output is correct |
36 |
Correct |
9 ms |
20564 KB |
Output is correct |
37 |
Correct |
9 ms |
20564 KB |
Output is correct |
38 |
Correct |
9 ms |
20564 KB |
Output is correct |
39 |
Correct |
9 ms |
20564 KB |
Output is correct |
40 |
Correct |
9 ms |
20564 KB |
Output is correct |
41 |
Correct |
8 ms |
20564 KB |
Output is correct |
42 |
Correct |
9 ms |
20616 KB |
Output is correct |
43 |
Correct |
9 ms |
20644 KB |
Output is correct |
44 |
Correct |
9 ms |
20564 KB |
Output is correct |
45 |
Correct |
9 ms |
20592 KB |
Output is correct |
46 |
Correct |
9 ms |
20632 KB |
Output is correct |
47 |
Correct |
9 ms |
20564 KB |
Output is correct |
48 |
Correct |
9 ms |
20564 KB |
Output is correct |
49 |
Correct |
9 ms |
20564 KB |
Output is correct |
50 |
Correct |
8 ms |
20564 KB |
Output is correct |
51 |
Correct |
9 ms |
20692 KB |
Output is correct |
52 |
Correct |
10 ms |
20692 KB |
Output is correct |
53 |
Correct |
9 ms |
20692 KB |
Output is correct |
54 |
Correct |
15 ms |
22100 KB |
Output is correct |
55 |
Correct |
14 ms |
22036 KB |
Output is correct |
56 |
Correct |
66 ms |
34324 KB |
Output is correct |
57 |
Correct |
78 ms |
34320 KB |
Output is correct |
58 |
Correct |
69 ms |
34252 KB |
Output is correct |
59 |
Correct |
65 ms |
33180 KB |
Output is correct |
60 |
Correct |
63 ms |
34240 KB |
Output is correct |
61 |
Correct |
67 ms |
34248 KB |
Output is correct |
62 |
Correct |
64 ms |
33096 KB |
Output is correct |
63 |
Correct |
65 ms |
33092 KB |
Output is correct |
64 |
Correct |
65 ms |
33088 KB |
Output is correct |
65 |
Correct |
65 ms |
34348 KB |
Output is correct |
66 |
Correct |
67 ms |
33168 KB |
Output is correct |
67 |
Correct |
65 ms |
33080 KB |
Output is correct |
68 |
Correct |
65 ms |
33112 KB |
Output is correct |
69 |
Correct |
10 ms |
20564 KB |
Output is correct |
70 |
Correct |
9 ms |
20564 KB |
Output is correct |
71 |
Correct |
68 ms |
33100 KB |
Output is correct |
72 |
Correct |
67 ms |
33100 KB |
Output is correct |
73 |
Correct |
65 ms |
33184 KB |
Output is correct |
74 |
Correct |
9 ms |
20564 KB |
Output is correct |
75 |
Correct |
8 ms |
20564 KB |
Output is correct |
76 |
Correct |
9 ms |
20620 KB |
Output is correct |
77 |
Correct |
9 ms |
20564 KB |
Output is correct |
78 |
Correct |
53 ms |
33164 KB |
Output is correct |
79 |
Correct |
70 ms |
33176 KB |
Output is correct |
80 |
Correct |
53 ms |
33104 KB |
Output is correct |
81 |
Correct |
62 ms |
33064 KB |
Output is correct |
82 |
Correct |
53 ms |
33188 KB |
Output is correct |
83 |
Correct |
60 ms |
33076 KB |
Output is correct |
84 |
Correct |
8 ms |
20564 KB |
Output is correct |
85 |
Correct |
9 ms |
20560 KB |
Output is correct |
86 |
Correct |
9 ms |
20564 KB |
Output is correct |
87 |
Correct |
9 ms |
20692 KB |
Output is correct |
88 |
Correct |
9 ms |
20692 KB |
Output is correct |
89 |
Correct |
9 ms |
20684 KB |
Output is correct |
90 |
Correct |
10 ms |
20808 KB |
Output is correct |
91 |
Correct |
10 ms |
20732 KB |
Output is correct |
92 |
Correct |
9 ms |
20804 KB |
Output is correct |
93 |
Correct |
9 ms |
20704 KB |
Output is correct |
94 |
Correct |
11 ms |
20736 KB |
Output is correct |
95 |
Correct |
9 ms |
20692 KB |
Output is correct |
96 |
Correct |
9 ms |
20692 KB |
Output is correct |
97 |
Correct |
9 ms |
20716 KB |
Output is correct |
98 |
Correct |
10 ms |
20692 KB |
Output is correct |
99 |
Correct |
9 ms |
20800 KB |
Output is correct |
100 |
Correct |
9 ms |
20692 KB |
Output is correct |
101 |
Correct |
14 ms |
22100 KB |
Output is correct |
102 |
Correct |
15 ms |
22076 KB |
Output is correct |
103 |
Correct |
71 ms |
34244 KB |
Output is correct |
104 |
Correct |
59 ms |
34248 KB |
Output is correct |
105 |
Correct |
79 ms |
34240 KB |
Output is correct |
106 |
Correct |
53 ms |
33868 KB |
Output is correct |
107 |
Correct |
76 ms |
34244 KB |
Output is correct |
108 |
Correct |
68 ms |
34268 KB |
Output is correct |
109 |
Correct |
59 ms |
33188 KB |
Output is correct |
110 |
Correct |
65 ms |
33184 KB |
Output is correct |
111 |
Correct |
54 ms |
33100 KB |
Output is correct |
112 |
Correct |
84 ms |
34368 KB |
Output is correct |
113 |
Correct |
74 ms |
34248 KB |
Output is correct |
114 |
Correct |
52 ms |
33144 KB |
Output is correct |
115 |
Correct |
56 ms |
33100 KB |
Output is correct |