#include <bits/stdc++.h>
#include "shoes.h"
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;
const int maxn = 610000;
vector<int> pos[610000];
bitset<maxn> used;
int n;
namespace fen{
int bit[maxn];
void upd(int id,int x){
while(id < maxn){
bit[id]+=x;
id|=id+1;
}
}
int sum(int r){
int res = 0;
while(r>=0){
res+=bit[r];
r&=r+1;
r--;
}
return res;
}
int segm(int l,int r){
int ans = sum(r);
if(l)ans-=sum(l-1);
return ans;
}
}
int get_id(int x){
if(x > 0)return x;
else return -x+n;
}
long long count_swaps(std::vector<int> s) {
long long ans = 0;
n = s.size()/2;
set<pair<int,int> > qwe;
for(int i(0); i < s.size();i++){
qwe.insert({i,s[i]});
if(s[i] > 0)pos[s[i]].push_back(i);
else{
int id = get_id(s[i]);
pos[id].push_back(i);
}
}
for(int i(1); i <= 2*n;i++){
reverse(pos[i].begin(),pos[i].end());
}
while(qwe.size()){
if(used[qwe.begin()->first]){
qwe.erase(qwe.begin());
continue;
}
int now = -qwe.begin()->second;
int id = get_id(now);
int to_pos = pos[id].back();
pos[id].pop_back();
pos[get_id(-now)].pop_back();
int dist = (to_pos+fen::segm(to_pos,maxn-1))-(qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1));
//cout << "W " << (to_pos+fen::segm(to_pos,maxn-1)) << ' ' << (qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1)) << endl;
if(qwe.begin()->second < 0)dist--;
ans+=dist;
used[qwe.begin()->first] = 1;
used[to_pos] = 1;
fen::upd(to_pos,1);
//cout << ans << ' ' << dist << endl;
}
return ans;
}
/*
6
-2 2 2 -2 -2 2
*/
/*
main(){
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<int> v;
for(int i(0); i < n;i++){
int x; cin >> x;
v.push_back(x);
}
cout << count_swaps(v);
return 0;
}*/
/*
4
2 1 -1 -2
6
-2 2 2 -2 -2 2
*/
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < s.size();i++){
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14716 KB |
Output is correct |
3 |
Correct |
15 ms |
14712 KB |
Output is correct |
4 |
Correct |
17 ms |
14712 KB |
Output is correct |
5 |
Correct |
15 ms |
14712 KB |
Output is correct |
6 |
Correct |
19 ms |
14712 KB |
Output is correct |
7 |
Correct |
15 ms |
14712 KB |
Output is correct |
8 |
Correct |
16 ms |
14712 KB |
Output is correct |
9 |
Correct |
15 ms |
14712 KB |
Output is correct |
10 |
Correct |
15 ms |
14712 KB |
Output is correct |
11 |
Correct |
12 ms |
14712 KB |
Output is correct |
12 |
Correct |
16 ms |
14840 KB |
Output is correct |
13 |
Correct |
15 ms |
14712 KB |
Output is correct |
14 |
Correct |
15 ms |
14712 KB |
Output is correct |
15 |
Correct |
15 ms |
14712 KB |
Output is correct |
16 |
Correct |
14 ms |
14712 KB |
Output is correct |
17 |
Correct |
15 ms |
14712 KB |
Output is correct |
18 |
Correct |
15 ms |
14712 KB |
Output is correct |
19 |
Correct |
15 ms |
14712 KB |
Output is correct |
20 |
Correct |
15 ms |
14712 KB |
Output is correct |
21 |
Correct |
15 ms |
14712 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14712 KB |
Output is correct |
24 |
Correct |
14 ms |
14632 KB |
Output is correct |
25 |
Correct |
15 ms |
14712 KB |
Output is correct |
26 |
Correct |
15 ms |
14840 KB |
Output is correct |
27 |
Correct |
13 ms |
14712 KB |
Output is correct |
28 |
Correct |
15 ms |
14712 KB |
Output is correct |
29 |
Correct |
15 ms |
14840 KB |
Output is correct |
30 |
Correct |
15 ms |
14712 KB |
Output is correct |
31 |
Correct |
15 ms |
14736 KB |
Output is correct |
32 |
Correct |
15 ms |
14712 KB |
Output is correct |
33 |
Correct |
15 ms |
14712 KB |
Output is correct |
34 |
Correct |
15 ms |
14712 KB |
Output is correct |
35 |
Correct |
15 ms |
14712 KB |
Output is correct |
36 |
Correct |
13 ms |
14712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14716 KB |
Output is correct |
3 |
Correct |
15 ms |
14712 KB |
Output is correct |
4 |
Correct |
14 ms |
14712 KB |
Output is correct |
5 |
Correct |
19 ms |
14712 KB |
Output is correct |
6 |
Correct |
15 ms |
14712 KB |
Output is correct |
7 |
Correct |
15 ms |
14712 KB |
Output is correct |
8 |
Correct |
15 ms |
14712 KB |
Output is correct |
9 |
Correct |
15 ms |
14712 KB |
Output is correct |
10 |
Correct |
15 ms |
14712 KB |
Output is correct |
11 |
Correct |
15 ms |
14712 KB |
Output is correct |
12 |
Correct |
15 ms |
14716 KB |
Output is correct |
13 |
Correct |
15 ms |
14712 KB |
Output is correct |
14 |
Correct |
16 ms |
14844 KB |
Output is correct |
15 |
Correct |
15 ms |
14712 KB |
Output is correct |
16 |
Correct |
15 ms |
14736 KB |
Output is correct |
17 |
Correct |
15 ms |
14712 KB |
Output is correct |
18 |
Correct |
16 ms |
14812 KB |
Output is correct |
19 |
Correct |
16 ms |
14840 KB |
Output is correct |
20 |
Correct |
24 ms |
15864 KB |
Output is correct |
21 |
Correct |
24 ms |
15864 KB |
Output is correct |
22 |
Correct |
123 ms |
27208 KB |
Output is correct |
23 |
Correct |
119 ms |
27172 KB |
Output is correct |
24 |
Correct |
121 ms |
27232 KB |
Output is correct |
25 |
Correct |
121 ms |
26880 KB |
Output is correct |
26 |
Correct |
124 ms |
28520 KB |
Output is correct |
27 |
Correct |
125 ms |
28264 KB |
Output is correct |
28 |
Correct |
124 ms |
28144 KB |
Output is correct |
29 |
Correct |
117 ms |
28200 KB |
Output is correct |
30 |
Correct |
127 ms |
28112 KB |
Output is correct |
31 |
Correct |
129 ms |
28660 KB |
Output is correct |
32 |
Correct |
120 ms |
28216 KB |
Output is correct |
33 |
Correct |
114 ms |
27888 KB |
Output is correct |
34 |
Correct |
125 ms |
28160 KB |
Output is correct |
35 |
Correct |
16 ms |
14712 KB |
Output is correct |
36 |
Correct |
20 ms |
14712 KB |
Output is correct |
37 |
Correct |
115 ms |
28144 KB |
Output is correct |
38 |
Correct |
116 ms |
28208 KB |
Output is correct |
39 |
Correct |
116 ms |
28272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14712 KB |
Output is correct |
3 |
Correct |
15 ms |
14712 KB |
Output is correct |
4 |
Correct |
15 ms |
14712 KB |
Output is correct |
5 |
Correct |
189 ms |
32376 KB |
Output is correct |
6 |
Correct |
130 ms |
28792 KB |
Output is correct |
7 |
Correct |
187 ms |
33824 KB |
Output is correct |
8 |
Correct |
114 ms |
28148 KB |
Output is correct |
9 |
Correct |
190 ms |
33636 KB |
Output is correct |
10 |
Correct |
161 ms |
30456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14716 KB |
Output is correct |
3 |
Correct |
15 ms |
14712 KB |
Output is correct |
4 |
Correct |
17 ms |
14712 KB |
Output is correct |
5 |
Correct |
15 ms |
14712 KB |
Output is correct |
6 |
Correct |
19 ms |
14712 KB |
Output is correct |
7 |
Correct |
15 ms |
14712 KB |
Output is correct |
8 |
Correct |
16 ms |
14712 KB |
Output is correct |
9 |
Correct |
15 ms |
14712 KB |
Output is correct |
10 |
Correct |
15 ms |
14712 KB |
Output is correct |
11 |
Correct |
12 ms |
14712 KB |
Output is correct |
12 |
Correct |
16 ms |
14840 KB |
Output is correct |
13 |
Correct |
15 ms |
14712 KB |
Output is correct |
14 |
Correct |
15 ms |
14712 KB |
Output is correct |
15 |
Correct |
15 ms |
14712 KB |
Output is correct |
16 |
Correct |
14 ms |
14712 KB |
Output is correct |
17 |
Correct |
15 ms |
14712 KB |
Output is correct |
18 |
Correct |
15 ms |
14712 KB |
Output is correct |
19 |
Correct |
15 ms |
14712 KB |
Output is correct |
20 |
Correct |
15 ms |
14712 KB |
Output is correct |
21 |
Correct |
15 ms |
14712 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14712 KB |
Output is correct |
24 |
Correct |
14 ms |
14632 KB |
Output is correct |
25 |
Correct |
15 ms |
14712 KB |
Output is correct |
26 |
Correct |
15 ms |
14840 KB |
Output is correct |
27 |
Correct |
13 ms |
14712 KB |
Output is correct |
28 |
Correct |
15 ms |
14712 KB |
Output is correct |
29 |
Correct |
15 ms |
14840 KB |
Output is correct |
30 |
Correct |
15 ms |
14712 KB |
Output is correct |
31 |
Correct |
15 ms |
14736 KB |
Output is correct |
32 |
Correct |
15 ms |
14712 KB |
Output is correct |
33 |
Correct |
15 ms |
14712 KB |
Output is correct |
34 |
Correct |
15 ms |
14712 KB |
Output is correct |
35 |
Correct |
15 ms |
14712 KB |
Output is correct |
36 |
Correct |
13 ms |
14712 KB |
Output is correct |
37 |
Correct |
15 ms |
14712 KB |
Output is correct |
38 |
Correct |
15 ms |
14636 KB |
Output is correct |
39 |
Correct |
14 ms |
14712 KB |
Output is correct |
40 |
Correct |
16 ms |
14712 KB |
Output is correct |
41 |
Correct |
16 ms |
14840 KB |
Output is correct |
42 |
Correct |
15 ms |
14840 KB |
Output is correct |
43 |
Correct |
16 ms |
14840 KB |
Output is correct |
44 |
Correct |
18 ms |
14772 KB |
Output is correct |
45 |
Correct |
16 ms |
14784 KB |
Output is correct |
46 |
Correct |
20 ms |
14840 KB |
Output is correct |
47 |
Correct |
23 ms |
14916 KB |
Output is correct |
48 |
Correct |
15 ms |
14840 KB |
Output is correct |
49 |
Correct |
16 ms |
14840 KB |
Output is correct |
50 |
Correct |
17 ms |
14840 KB |
Output is correct |
51 |
Correct |
16 ms |
14712 KB |
Output is correct |
52 |
Correct |
17 ms |
14840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14712 KB |
Output is correct |
2 |
Correct |
15 ms |
14716 KB |
Output is correct |
3 |
Correct |
15 ms |
14712 KB |
Output is correct |
4 |
Correct |
17 ms |
14712 KB |
Output is correct |
5 |
Correct |
15 ms |
14712 KB |
Output is correct |
6 |
Correct |
19 ms |
14712 KB |
Output is correct |
7 |
Correct |
15 ms |
14712 KB |
Output is correct |
8 |
Correct |
16 ms |
14712 KB |
Output is correct |
9 |
Correct |
15 ms |
14712 KB |
Output is correct |
10 |
Correct |
15 ms |
14712 KB |
Output is correct |
11 |
Correct |
12 ms |
14712 KB |
Output is correct |
12 |
Correct |
16 ms |
14840 KB |
Output is correct |
13 |
Correct |
15 ms |
14712 KB |
Output is correct |
14 |
Correct |
15 ms |
14712 KB |
Output is correct |
15 |
Correct |
15 ms |
14712 KB |
Output is correct |
16 |
Correct |
14 ms |
14712 KB |
Output is correct |
17 |
Correct |
15 ms |
14712 KB |
Output is correct |
18 |
Correct |
15 ms |
14712 KB |
Output is correct |
19 |
Correct |
15 ms |
14712 KB |
Output is correct |
20 |
Correct |
15 ms |
14712 KB |
Output is correct |
21 |
Correct |
15 ms |
14712 KB |
Output is correct |
22 |
Correct |
15 ms |
14712 KB |
Output is correct |
23 |
Correct |
15 ms |
14712 KB |
Output is correct |
24 |
Correct |
14 ms |
14632 KB |
Output is correct |
25 |
Correct |
15 ms |
14712 KB |
Output is correct |
26 |
Correct |
15 ms |
14840 KB |
Output is correct |
27 |
Correct |
13 ms |
14712 KB |
Output is correct |
28 |
Correct |
15 ms |
14712 KB |
Output is correct |
29 |
Correct |
15 ms |
14840 KB |
Output is correct |
30 |
Correct |
15 ms |
14712 KB |
Output is correct |
31 |
Correct |
15 ms |
14736 KB |
Output is correct |
32 |
Correct |
15 ms |
14712 KB |
Output is correct |
33 |
Correct |
15 ms |
14712 KB |
Output is correct |
34 |
Correct |
15 ms |
14712 KB |
Output is correct |
35 |
Correct |
15 ms |
14712 KB |
Output is correct |
36 |
Correct |
13 ms |
14712 KB |
Output is correct |
37 |
Correct |
15 ms |
14712 KB |
Output is correct |
38 |
Correct |
14 ms |
14712 KB |
Output is correct |
39 |
Correct |
19 ms |
14712 KB |
Output is correct |
40 |
Correct |
15 ms |
14712 KB |
Output is correct |
41 |
Correct |
15 ms |
14712 KB |
Output is correct |
42 |
Correct |
15 ms |
14712 KB |
Output is correct |
43 |
Correct |
15 ms |
14712 KB |
Output is correct |
44 |
Correct |
15 ms |
14712 KB |
Output is correct |
45 |
Correct |
15 ms |
14712 KB |
Output is correct |
46 |
Correct |
15 ms |
14716 KB |
Output is correct |
47 |
Correct |
15 ms |
14712 KB |
Output is correct |
48 |
Correct |
16 ms |
14844 KB |
Output is correct |
49 |
Correct |
15 ms |
14712 KB |
Output is correct |
50 |
Correct |
15 ms |
14736 KB |
Output is correct |
51 |
Correct |
15 ms |
14712 KB |
Output is correct |
52 |
Correct |
16 ms |
14812 KB |
Output is correct |
53 |
Correct |
16 ms |
14840 KB |
Output is correct |
54 |
Correct |
24 ms |
15864 KB |
Output is correct |
55 |
Correct |
24 ms |
15864 KB |
Output is correct |
56 |
Correct |
123 ms |
27208 KB |
Output is correct |
57 |
Correct |
119 ms |
27172 KB |
Output is correct |
58 |
Correct |
121 ms |
27232 KB |
Output is correct |
59 |
Correct |
121 ms |
26880 KB |
Output is correct |
60 |
Correct |
124 ms |
28520 KB |
Output is correct |
61 |
Correct |
125 ms |
28264 KB |
Output is correct |
62 |
Correct |
124 ms |
28144 KB |
Output is correct |
63 |
Correct |
117 ms |
28200 KB |
Output is correct |
64 |
Correct |
127 ms |
28112 KB |
Output is correct |
65 |
Correct |
129 ms |
28660 KB |
Output is correct |
66 |
Correct |
120 ms |
28216 KB |
Output is correct |
67 |
Correct |
114 ms |
27888 KB |
Output is correct |
68 |
Correct |
125 ms |
28160 KB |
Output is correct |
69 |
Correct |
16 ms |
14712 KB |
Output is correct |
70 |
Correct |
20 ms |
14712 KB |
Output is correct |
71 |
Correct |
115 ms |
28144 KB |
Output is correct |
72 |
Correct |
116 ms |
28208 KB |
Output is correct |
73 |
Correct |
116 ms |
28272 KB |
Output is correct |
74 |
Correct |
15 ms |
14712 KB |
Output is correct |
75 |
Correct |
15 ms |
14712 KB |
Output is correct |
76 |
Correct |
15 ms |
14712 KB |
Output is correct |
77 |
Correct |
15 ms |
14712 KB |
Output is correct |
78 |
Correct |
189 ms |
32376 KB |
Output is correct |
79 |
Correct |
130 ms |
28792 KB |
Output is correct |
80 |
Correct |
187 ms |
33824 KB |
Output is correct |
81 |
Correct |
114 ms |
28148 KB |
Output is correct |
82 |
Correct |
190 ms |
33636 KB |
Output is correct |
83 |
Correct |
161 ms |
30456 KB |
Output is correct |
84 |
Correct |
15 ms |
14712 KB |
Output is correct |
85 |
Correct |
15 ms |
14636 KB |
Output is correct |
86 |
Correct |
14 ms |
14712 KB |
Output is correct |
87 |
Correct |
16 ms |
14712 KB |
Output is correct |
88 |
Correct |
16 ms |
14840 KB |
Output is correct |
89 |
Correct |
15 ms |
14840 KB |
Output is correct |
90 |
Correct |
16 ms |
14840 KB |
Output is correct |
91 |
Correct |
18 ms |
14772 KB |
Output is correct |
92 |
Correct |
16 ms |
14784 KB |
Output is correct |
93 |
Correct |
20 ms |
14840 KB |
Output is correct |
94 |
Correct |
23 ms |
14916 KB |
Output is correct |
95 |
Correct |
15 ms |
14840 KB |
Output is correct |
96 |
Correct |
16 ms |
14840 KB |
Output is correct |
97 |
Correct |
17 ms |
14840 KB |
Output is correct |
98 |
Correct |
16 ms |
14712 KB |
Output is correct |
99 |
Correct |
17 ms |
14840 KB |
Output is correct |
100 |
Correct |
16 ms |
14840 KB |
Output is correct |
101 |
Correct |
28 ms |
16504 KB |
Output is correct |
102 |
Correct |
27 ms |
16224 KB |
Output is correct |
103 |
Correct |
213 ms |
33912 KB |
Output is correct |
104 |
Correct |
196 ms |
34012 KB |
Output is correct |
105 |
Correct |
186 ms |
31324 KB |
Output is correct |
106 |
Correct |
192 ms |
33664 KB |
Output is correct |
107 |
Correct |
145 ms |
29404 KB |
Output is correct |
108 |
Correct |
157 ms |
29696 KB |
Output is correct |
109 |
Correct |
115 ms |
28272 KB |
Output is correct |
110 |
Correct |
116 ms |
28144 KB |
Output is correct |
111 |
Correct |
170 ms |
32816 KB |
Output is correct |
112 |
Correct |
183 ms |
32720 KB |
Output is correct |
113 |
Correct |
145 ms |
29040 KB |
Output is correct |
114 |
Correct |
196 ms |
33660 KB |
Output is correct |
115 |
Correct |
193 ms |
33628 KB |
Output is correct |