| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 599662 | OrazB | Arranging Shoes (IOI19_shoes) | C++14 | 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"
#define N 400005
#define wr cout << "Continue debugging\n";
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
using namespace std;
int t[N], s[N], vis[N];
vector <int> a, v1[N], v2[N];
void build(int l, int r, int idx){
if (l == r){t[idx] = 1; return;}
int md = (l + r) / 2;
build(l, md, idx*2);
build(md+1, r, idx*2+1);
t[idx] = t[idx*2] + t[idx*2+1];
}
int sum(int a, int b, int l, int r, int idx){
if (r < a or l > b) return 0;
if (l >= a and r <= b) return t[idx];
int md = (l + r) / 2;
return sum(a, b, l, md, idx*2) + sum(a, b, md+1, r, idx*2+1);
}
void upd(int nd, int l, int r, int idx){
int md = (l + r) / 2;
if (l == r){t[idx] = 0; return;}
if (nd <= md) upd(nd, l, md, idx*2);
else upd(nd, md+1, r, idx*2+1);
t[idx] = t[idx*2] + t[idx*2+1];
}
int count_swaps(vector <int> a){
int n = a.size(), ans = 0;
for (int i = 0; i < n; i++){
if (a[i] < 0) v1[-a[i]].pb(i);
else v2[a[i]].pb(i);
}
build(0, n-1, 1);
for (int i = 1; i <= n; i++){
reverse(v1[i].begin(), v1[i].end());
reverse(v2[i].begin(), v2[i].end());
}
for (int i = 0; i < n; i++){
if (vis[i]) continue;
int idx = 0;
if (a[i] < 0){
idx = v2[-a[i]].back();
ans += sum(i+1, idx-1, 0, n-1, 1);
}else{
idx = v1[a[i]].back();
ans += sum(i+1, idx-1, 0, n-1, 1)+1;
}
v2[abs(a[i])].pop_back();
v1[abs(a[i])].pop_back();
vis[idx] = 1;
upd(idx, 0, n-1, 1);
}
return ans;
}
// int main ()
// {
// int n1;
// cin >> n1;
// for (int i = 1; i <= n1; i++) cin >> s[i], a.pb(s[i]);
// cout << count_swaps(a);
// }