#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> l[200001],r[200001];
vector<pair<int,int> > p;
int t[800001];
void update(int i,int l,int r,int id)
{
if(l==r)
{
t[i]=1;
return;
}
int m=(l+r)/2;
if(id<=m)update(i*2,l,m,id);
else update(i*2+1,m+1,r,id);
t[i]=t[i*2]+t[i*2+1];
}
long long query(int i,int l,int r,int ql,int qr)
{
if(ql>qr)return 0;
if(ql<=l&&r<=qr)return t[i];
int m=(l+r)/2;
return query(i*2,l,m,ql,min(qr,m))+query(i*2+1,m+1,r,max(m+1,ql),qr);
}
long long count_swaps(std::vector<int> s)
{
for(int i=0;i<s.size();i++)
{
if(s[i]<0)l[-s[i]].push_back(i);
else r[s[i]].push_back(i);
}
long long ans=0;
vector<pair<int,int> > v;
for(int i=0;i<s.size();i++)
{
for(int j=0;j<l[i].size();j++)
{
if(l[i][j]>r[i][j])ans++;
v.push_back({min(l[i][j],r[i][j]),max(l[i][j],r[i][j])});
}
}
for(int i=0;i<v.size();i++)
p.push_back({v[i].first,-1}),
p.push_back({v[i].second,v[i].first});
sort(p.begin(),p.end());
int open=0;
for(int i=0;i<p.size();i++)
{
if(p[i].second==-1)open++;
else
{
open--;
ans+=open;
ans+=query(1,0,s.size()-1,p[i].second,p[i].first);
update(1,0,s.size()-1,p[i].second);
//cout<<p[i].second<<" + "<<p[i].second<<" "<<p[i].first<<endl;
}
}
return 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... |