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>
#define ll long long
using namespace std;
ll n;
struct bit
{
vector<ll> v;
void Init()
{
v.resize(n+5);
}
void Add(ll pos,ll val)
{
for (ll i=pos;i<=n;i+=i&(-i))
v[i]+=val;
}
ll Sum(ll pos)
{
ll ans=0;
for (ll i=pos;i>0;i-=i&(-i))
ans+=v[i];
return ans;
}
ll Calc(ll l,ll r)
{
return Sum(r)-Sum(l-1);
}
};
ll count_swaps(vector<int> S)
{
n=sizeof(S);
bit B;
B.Init();
map<ll,queue<ll> > posl,posr;
ll ans=0;
for (ll i=0;i<n;i++)
{
if (S[i]>0)
{
if (posl[S[i]].empty())
{
B.Add(i+1,1);
posr[S[i]].push(i+1);
continue;
}
ll t=posl[S[i]].front();
posl[S[i]].pop();
ans+=B.Calc(t+1,i+1);
B.Add(t,-1);
continue;
}
if (posr[-S[i]].empty())
{
B.Add(i+1,1);
posl[-S[i]].push(i+1);
continue;
}
ll t=posr[-S[i]].front();
posr[-S[i]].pop();
ans+=B.Calc(t,i+1);
B.Add(t,-1);
}
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... |