| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 825769 | vjudge1 | 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 "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 18);
int t[2 * N + 100], sum[2 * N + 100], p = 0;
vector <int> S;
void build (int x, int tl, int tr){
if (tl == tr){
t[x] = tl;
}
else{
int mid = (tl + tr)/2;
build(x * 2, tl, mid);
build(x * 2 + 1, mid + 1, tr);
t[x] = t[2 * x] + t[2 * x + 1];
}
}
void update(int l, int r, int x, int tl, int tr){
if (l > r){
return ;
}
else if (l == tl && r == tr){
sum[x]++;
}
else{
//cout << l << " " << r << " " << x << " " << tl << " " << tr << "\n";
int tmid = (tl + tr)/2;
update(l, min(tmid, r), x * 2, tl, tmid);
update(max(l, tmid + 1), r, x * 2 + 1, tmid + 1, tr);
}
}
int get(int num, int x, int tl, int tr){
if (tl == tr){
p+=sum[x];
return t[x] + sum[x];
}
else{
p+=sum[x];
int tmid = (tl + tr)/2;
if (num > tmid)
return get(num, x * 2 + 1, tmid + 1, tr) + sum[x];
else
return get(num, x * 2, tl, tmid) + sum[x];
}
}
int count_swaps(vector<int> s) {
int ans = 0, n = s.size();
map <int, deque <int>> mp;
int used[n];
build(1, 0, n - 1);
for (int i = 0 ; i < n ; i++){
used[i] = 0;
//cout << get(i, 1, 0, n - 1) << "\n";
mp[s[i]].push_back(i);
}
for (int i = 0 ; i < n ; i++){
if (used[i])
continue ;
int cur1 = i, cur2 = mp[s[i] * -1][0];
mp[s[i] * -1].pop_front();
mp[s[i]].pop_front();
//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
ans+=max(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - min(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - 1;
update(min(cur1, cur2), max(cur1, cur2), 1, 0, n - 1);
//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
used[cur1] = 1;
used[cur2] = 1;
if (s[i] > 0)
ans++;
}
return ans;
}