# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
794564 | Pablo_No | Arranging Shoes (IOI19_shoes) | C++17 | 88 ms | 17992 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5+5;
set<int> p[2*N];
int ft[2*N];
void add(int p, int v)
{
while(p < 2*N)
{
ft[p] += v;
p += (p & (-p));
}
}
int rsq(int p)
{
int ans = 0;
while(p)
{
ans += ft[p];
p -= (p & (-p));
}
return ans;
}
long long count_swaps(std::vector<int> s) {
long long ans = 0;
for(int i = 0; i < s.size(); i++)
{
int ai = s[i];
if(!p[-ai+N].empty())
{
int fp = *p[-ai+N].begin();
//cerr << rsq(fp+1) << '\n';
ans += (i-fp)-(ai > 0)-rsq(fp+1);
add(fp+2, 1);
add(i+1, -1);
p[-ai+N].erase(fp);
}
else
{
p[ai+N].insert(i);
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |