#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define S second
#define F first
using namespace std;
ll tree[800045];
ll lazy[800045];
map < ll, vector<ll> > vc;
void update( ll L, ll R, ll l, ll r, ll node ){
// cout << "range:" << l << " " << r << "\n";
if( L <= l && r <= R ){
// cout << " " << l << " " << r << " " << node << "\n";
// if( l == r )
// tree[node] ++;
// else
lazy[node] ++;
return;
}
if( R < l || r < L )
return;
if( R < L )
return;
ll mid = (l+r)/2;
update( L, R, l, mid, node*2 );
update( L, R, mid+1, r, node*2+1 );
}
ll cnt = 0;
ll query( ll idx, ll l, ll r, ll node ){
if( l == r ){
tree[node] += lazy[node];
lazy[node] = 0;
return tree[node];
}
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
lazy[node] = 0;
ll mid = (l+r)/2;
if( l <= idx && idx <= mid )
return query( idx, l, mid, node*2 );
return query( idx, mid+1, r, node*2+1 );
}
long long count_swaps(std::vector<int> a) {
ll n = a.size()/2;
ll ans = 0;
for(int i = -n; i <= n; i ++ ){
vc[i].pb( 1 );
}
for(int i = 0; i < a.size(); i ++ ){
vc[ a[i] ].pb( i );
}
n = a.size();
for(int i = 0; i < a.size(); i ++ ){
if( a[i] == 0 )
continue;
ll j = vc[ -a[i] ][ vc[a[i]][0] ];
// cout << "num " << a[i] << "\n";
// cout << "real " << i << " " << j << "\n";
a[j] = 0;
ll nj = j + query( j, 0, n-1, 1 );
ll ni = i + query( i, 0, n-1, 1 );
// cout << "new " << ni << " " << nj << "\n";
ans += nj-ni;
if( a[i] < 0 )
ans --;
// cout << "updated" << i+1 << " " << j-1 << "\n";
update( i+1, j-1, 0, n-1, 1 );
vc[ a[i] ][ 0 ] ++;
vc[ -a[i] ][ 0 ] ++;
// cout << "tree\n";
// for(int k = 1; k <= 33; k ++ ){
// cout << k << ":" << tree[k] << " ";
// }
// for(int k = 40; k <= 41; k ++ ){
// cout << k << ":" << tree[k] << " ";
// }
// for(int k = 48; k <= 49; k ++ ){
// cout << k << ":" << tree[k] << " ";
// }
// for(int k = 56; k <= 57; k ++ ){
// cout << k << ":" << tree[k] << " ";
// }
// cout << "\n";
// cout << "lazy\n";
// for(int k = 1; k <= 33; k ++ ){
// cout << k << ":" << lazy[k] << " ";
// }
// for(int k = 40; k <= 41; k ++ ){
// cout << k << ":" << lazy[k] << " ";
// }
// for(int k = 48; k <= 49; k ++ ){
// cout << k << ":" << lazy[k] << " ";
// }
// for(int k = 56; k <= 57; k ++ ){
// cout << k << ":" << lazy[k] << " ";
// }
// cout << "\n";
}
return ans;
}
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < a.size(); i ++ ){
| ~~^~~~~~~~~~
shoes.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < a.size(); i ++ ){
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
440 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
9 ms |
5788 KB |
Output is correct |
21 |
Correct |
10 ms |
5784 KB |
Output is correct |
22 |
Correct |
118 ms |
34112 KB |
Output is correct |
23 |
Correct |
104 ms |
34208 KB |
Output is correct |
24 |
Correct |
114 ms |
34236 KB |
Output is correct |
25 |
Correct |
120 ms |
34024 KB |
Output is correct |
26 |
Correct |
117 ms |
34220 KB |
Output is correct |
27 |
Correct |
105 ms |
34072 KB |
Output is correct |
28 |
Correct |
126 ms |
34088 KB |
Output is correct |
29 |
Correct |
118 ms |
34000 KB |
Output is correct |
30 |
Correct |
124 ms |
34120 KB |
Output is correct |
31 |
Correct |
119 ms |
34088 KB |
Output is correct |
32 |
Correct |
121 ms |
34244 KB |
Output is correct |
33 |
Correct |
139 ms |
33976 KB |
Output is correct |
34 |
Correct |
127 ms |
34000 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
444 KB |
Output is correct |
37 |
Correct |
128 ms |
34220 KB |
Output is correct |
38 |
Correct |
126 ms |
33996 KB |
Output is correct |
39 |
Correct |
130 ms |
34056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
292 ms |
32420 KB |
Output is correct |
6 |
Correct |
297 ms |
35108 KB |
Output is correct |
7 |
Correct |
306 ms |
32364 KB |
Output is correct |
8 |
Correct |
136 ms |
34680 KB |
Output is correct |
9 |
Correct |
278 ms |
32276 KB |
Output is correct |
10 |
Correct |
300 ms |
35672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
440 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
444 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
2 ms |
604 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
2 ms |
600 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
1 ms |
604 KB |
Output is correct |
46 |
Correct |
1 ms |
604 KB |
Output is correct |
47 |
Correct |
2 ms |
604 KB |
Output is correct |
48 |
Correct |
1 ms |
604 KB |
Output is correct |
49 |
Correct |
2 ms |
604 KB |
Output is correct |
50 |
Correct |
1 ms |
648 KB |
Output is correct |
51 |
Correct |
1 ms |
604 KB |
Output is correct |
52 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
440 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
348 KB |
Output is correct |
44 |
Correct |
0 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
1 ms |
344 KB |
Output is correct |
48 |
Correct |
1 ms |
344 KB |
Output is correct |
49 |
Correct |
1 ms |
348 KB |
Output is correct |
50 |
Correct |
0 ms |
344 KB |
Output is correct |
51 |
Correct |
1 ms |
348 KB |
Output is correct |
52 |
Correct |
1 ms |
600 KB |
Output is correct |
53 |
Correct |
1 ms |
600 KB |
Output is correct |
54 |
Correct |
9 ms |
5788 KB |
Output is correct |
55 |
Correct |
10 ms |
5784 KB |
Output is correct |
56 |
Correct |
118 ms |
34112 KB |
Output is correct |
57 |
Correct |
104 ms |
34208 KB |
Output is correct |
58 |
Correct |
114 ms |
34236 KB |
Output is correct |
59 |
Correct |
120 ms |
34024 KB |
Output is correct |
60 |
Correct |
117 ms |
34220 KB |
Output is correct |
61 |
Correct |
105 ms |
34072 KB |
Output is correct |
62 |
Correct |
126 ms |
34088 KB |
Output is correct |
63 |
Correct |
118 ms |
34000 KB |
Output is correct |
64 |
Correct |
124 ms |
34120 KB |
Output is correct |
65 |
Correct |
119 ms |
34088 KB |
Output is correct |
66 |
Correct |
121 ms |
34244 KB |
Output is correct |
67 |
Correct |
139 ms |
33976 KB |
Output is correct |
68 |
Correct |
127 ms |
34000 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
0 ms |
444 KB |
Output is correct |
71 |
Correct |
128 ms |
34220 KB |
Output is correct |
72 |
Correct |
126 ms |
33996 KB |
Output is correct |
73 |
Correct |
130 ms |
34056 KB |
Output is correct |
74 |
Correct |
0 ms |
348 KB |
Output is correct |
75 |
Correct |
0 ms |
348 KB |
Output is correct |
76 |
Correct |
0 ms |
348 KB |
Output is correct |
77 |
Correct |
1 ms |
348 KB |
Output is correct |
78 |
Correct |
292 ms |
32420 KB |
Output is correct |
79 |
Correct |
297 ms |
35108 KB |
Output is correct |
80 |
Correct |
306 ms |
32364 KB |
Output is correct |
81 |
Correct |
136 ms |
34680 KB |
Output is correct |
82 |
Correct |
278 ms |
32276 KB |
Output is correct |
83 |
Correct |
300 ms |
35672 KB |
Output is correct |
84 |
Correct |
1 ms |
444 KB |
Output is correct |
85 |
Correct |
1 ms |
348 KB |
Output is correct |
86 |
Correct |
0 ms |
348 KB |
Output is correct |
87 |
Correct |
1 ms |
348 KB |
Output is correct |
88 |
Correct |
2 ms |
604 KB |
Output is correct |
89 |
Correct |
1 ms |
604 KB |
Output is correct |
90 |
Correct |
2 ms |
600 KB |
Output is correct |
91 |
Correct |
1 ms |
604 KB |
Output is correct |
92 |
Correct |
1 ms |
604 KB |
Output is correct |
93 |
Correct |
1 ms |
604 KB |
Output is correct |
94 |
Correct |
2 ms |
604 KB |
Output is correct |
95 |
Correct |
1 ms |
604 KB |
Output is correct |
96 |
Correct |
2 ms |
604 KB |
Output is correct |
97 |
Correct |
1 ms |
648 KB |
Output is correct |
98 |
Correct |
1 ms |
604 KB |
Output is correct |
99 |
Correct |
1 ms |
604 KB |
Output is correct |
100 |
Correct |
2 ms |
604 KB |
Output is correct |
101 |
Correct |
17 ms |
5500 KB |
Output is correct |
102 |
Correct |
18 ms |
5724 KB |
Output is correct |
103 |
Correct |
394 ms |
32524 KB |
Output is correct |
104 |
Correct |
286 ms |
32336 KB |
Output is correct |
105 |
Correct |
339 ms |
35608 KB |
Output is correct |
106 |
Correct |
296 ms |
32372 KB |
Output is correct |
107 |
Correct |
302 ms |
35112 KB |
Output is correct |
108 |
Correct |
290 ms |
35452 KB |
Output is correct |
109 |
Correct |
127 ms |
34832 KB |
Output is correct |
110 |
Correct |
118 ms |
34208 KB |
Output is correct |
111 |
Correct |
302 ms |
33352 KB |
Output is correct |
112 |
Correct |
353 ms |
34384 KB |
Output is correct |
113 |
Correct |
301 ms |
35120 KB |
Output is correct |
114 |
Correct |
299 ms |
32512 KB |
Output is correct |
115 |
Correct |
292 ms |
32292 KB |
Output is correct |