#include "shoes.h"
#include <queue>
#include <iostream>
#define mx 100000
using namespace std;
queue<int> ns[200005];
int fn[200005];
long long qr(int n, int x)
{
int rez = 0;
for (int i = x+1; i; i-=(i&-i))
rez += fn[i];
return rez;
}
void upd(int n, int x)
{
for (int i = x+1; i <= n; i+=(i&-i))
fn[x]++;
}
long long count_swaps(vector<int> s)
{
int n = s.size();
for (int i = 0; i < n; i++)
ns[s[i]+mx].push(i);
int rez = 0;
for (int i = 0; i < n; i++)
{
if (ns[s[i]+mx].empty() || ns[s[i]+mx].front() != i)
continue;
ns[s[i]+mx].pop();
int par = s[i]*-1+mx;
rez += ns[par].front()-i-qr(n, i)+qr(n, ns[par].front())-1;
// cout << i << ": " << ns[par].front()-i-qr(n, i)+qr(n, ns[par].front())-1 << "\n";
upd(n, ns[par].front());
ns[par].pop();
if (s[i] > 0 && i%2 == 0)
rez++;
if (s[i] < 0 && i%2 == 1)
rez++;
}
return rez;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
135504 KB |
Output is correct |
2 |
Correct |
63 ms |
135456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
135504 KB |
Output is correct |
2 |
Correct |
63 ms |
135456 KB |
Output is correct |
3 |
Incorrect |
67 ms |
135508 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
135504 KB |
Output is correct |
2 |
Correct |
63 ms |
135456 KB |
Output is correct |
3 |
Correct |
65 ms |
135616 KB |
Output is correct |
4 |
Correct |
66 ms |
135504 KB |
Output is correct |
5 |
Correct |
62 ms |
135580 KB |
Output is correct |
6 |
Correct |
68 ms |
135508 KB |
Output is correct |
7 |
Correct |
62 ms |
135572 KB |
Output is correct |
8 |
Correct |
71 ms |
135656 KB |
Output is correct |
9 |
Incorrect |
63 ms |
135600 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
135660 KB |
Output is correct |
2 |
Correct |
62 ms |
135504 KB |
Output is correct |
3 |
Correct |
66 ms |
135552 KB |
Output is correct |
4 |
Correct |
68 ms |
135424 KB |
Output is correct |
5 |
Incorrect |
124 ms |
138324 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
135504 KB |
Output is correct |
2 |
Correct |
63 ms |
135456 KB |
Output is correct |
3 |
Incorrect |
67 ms |
135508 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
135504 KB |
Output is correct |
2 |
Correct |
63 ms |
135456 KB |
Output is correct |
3 |
Incorrect |
67 ms |
135508 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |