| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1319543 | yessimkhan | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "shoes.h"
#include <bits/stdc++.h>
// solved by bekagg
#define ll long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 4e5+5;
const int MOD = 1e9+7;
int t[4 * N] , ans;
bool us[N];
set<int>p[N][2];
void build(int v , int tl , int tr){
t[v] = tr - tl + 1;
if (tl == tr) return;
int tm = (tl + tr) / 2;
build(v * 2 , tl , tm) , build(v * 2 + 1 , tm + 1 , tr);
}
void update(int v , int tl , int tr , int i , int x){
if (tl == tr){
t[v] = x;
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) update(v * 2 , tl , tm , i , x);
else update(v * 2 + 1 , tm + 1 , tr , i , x);
t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v , int tl , int tr , int l , int r){
if (tr < l or r < tl) return 0;
if (l <= tl and tr <= r) return t[v];
int tm = (tl + tr) / 2;
return get(v * 2 , tl , tm , l , r) + get(v * 2 + 1 , tm + 1 , tr , l , r);
}
int64 count_swaps(vector<int> a){
build(1 , 1 , a.size());
for (int i = 1; i <= a.size(); i++){
p[abs(a[i - 1])][(a[i - 1] > 0)].insert(i);
}
for (int i = 1; i <= a.size(); i++){
if (us[i]) continue;
update(1 , 1 , n , i , 0);
auto it = p[abs(a[i - 1])][(a[i - 1] < 0)].upper_bound(i);
update(1 , 1 , n , *it , 0);
ans += get(1 , 1 , n , i , *it);
us[*it] = 1;
p[abs(a[i - 1])][(a[i - 1] < 0)].erase(it);
}
return ans;
}