#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+qr(n, i))%2 == 0)
rez++;
if (s[i] < 0 && (i+qr(n, i))%2 == 1)
rez++;
}
return rez;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
135508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
135508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
135508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
135512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
135508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
135508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |