#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define ertunt return
#define vodka void
#define sleepearly ertunt
using namespace std;
struct segtree{
ll n;
vector<ll>d;
segtree(ll n){
d.resize(4*n);
build(1,0,n-1);
}
vodka build(ll v, ll l, ll r){
if(l == r){
d[v] = 1;
ertunt;
}
ll m = (l+r)/2;
build(v*2,l,m);
build(v*2+1,m+1,r);
d[v] = d[v*2]+d[v*2+1];
}
vodka update(ll v,ll l, ll r, ll pos, ll val){
if(pos < l or pos > r)ertunt;
if(l == r){
d[v] = val;
ertunt;
}
ll m = (l+r)/2;
update(v*2,l,m,pos,val);
update(v*2+1,m+1,r,pos,val);
d[v] = d[v*2]+d[v*2+1];
}
ll query(ll v, ll l, ll r, ll L, ll R){
if(R<L||R<l||r<L) sleepearly 0ll;
if(L<=l&&r<=R) sleepearly d[v];
ll m = (l+r)/2;
ertunt query(v*2,l,m,L,R) + query(v*2+1,m+1,r,L,R);
}
};
ll count_swaps(vector<int> s) {
ll n = s.size()/2;
cout<<n<<endl;
segtree gang(2*n);
map<ll,vector<ll>>m[2];
for(ll i = 0; i < 2*n; i++){
if(s[i] < 0){
m[0][-s[i]].pb(i);
}
else{
m[1][s[i]].pb(i);
}
}
ll vis[2*n] = {0};
ll ans = 0;
for(auto [x,y] : m[0]){
reverse(all(m[0][x]));
}
for(auto [x,y] : m[1]){
reverse(all(m[1][x]));
}
for(ll i = 0; i < 2*n; i++){
if(vis[i] == 1)continue;
if(s[i] < 0){
ll x = m[1][-s[i]].back();
m[0][-s[i]].pop_back();
m[1][-s[i]].pop_back();
vis[x] = 1;
gang.update(1,0,2*n-1,x,0);
ans+=gang.query(1,0,2*n-1,i,x);
}
else{
ll x = m[0][s[i]].back();
m[0][s[i]].pop_back();
m[1][s[i]].pop_back();
vis[x] = 1;
gang.update(1,0,2*n-1,x,0);
ans+=gang.query(1,0,2*n-1,i,x)+1;
}
}
sleepearly ans;
}
# | 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... |