| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839151 | DarkMatter | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 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<bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
vector<ll>seg;
void update(int i, ll v, int x, int lx, int rx) {
if (lx + 1 == rx) {
seg[i] = v;
return;
}
int mid = (lx + rx) / 2, idx1 = 2 * x + 1, idx2 = 2 * x + 2;
if (i < mid)
update(i, v, idx1, lx, mid);
else
update(i, v, idx2, mid, rx);
seg[x] = seg[idx1] + seg[idx2];
}
ll get(int l, int r, int x, int lx, int rx) {
if (lx >= r || rx <= l)
return 0;
if (lx >= l && rx <= r)
return seg[x];
int mid = (lx + rx), idx1 = 2 * x + 1, idx2 = 2 * x + 2;
return (get(l, r, idx1, lx, mid) + get(l, r, idx2, mid, rx));
}
long long count_swaps(std::vector<int> v) {
int n = v.size();
vector<bool>vis(n, false);
int siz = 1;
while (siz < n)
siz *= 2;
seg.resize(2 * siz, 0);
for (int i = 0; i < n; i++)
update(i, i, 0, 0, siz);
map<int, priority_queue<int>>idx;
for (int i = 0; i < n; i++)
idx[v[i]].push(i);
vector<bool>vis(n + 1, false);
for (int i = 0; i < n; i++) {
if (vis[i])
continue;
int j = idx[-v[i]].top();
vis[i] = vis[j] = true;
idx[-v[i]].pop();
ll valJ = get(0, j + 1, 0, 0, siz), valI = get(0, i + 1, 0, 0, siz);
ll dif = valJ - valI;
if (valI % 2 == 0 && v[i] < 0)
ans += dif;
else
ans += dif + 1;
update(i + 1, 1, 0, 0, siz);
update(j + 1, -1, 0, 0, siz);
}
return ans;
}