Submission #721419

#	Time	Username	Problem	Language	Result	Execution time	Memory
721419		sofija6	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	629 ms	148756 KiB

shoes

#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=S.size();
    bit B;
    B.Init();
    map<ll,queue<ll> > posl,posr;
    ll ans=0;
    for (ll i=0;i<n;i++)
    {
        if (S[i]>0)
            posr[S[i]].push(i+1);
        else
            posl[-S[i]].push(i+1);
        B.Add(i+1,1);
    }
    for (ll i=0;i<n;i++)
    {
        if (S[i]>0 && (!posr[S[i]].empty() && posr[S[i]].front()==i+1))
        {
            ans+=B.Calc(i+1,posl[S[i]].front()-1);
            B.Add(posl[S[i]].front(),-1);
            posl[S[i]].pop();
            posr[S[i]].pop();
            continue;
        }
        if (S[i]<0 && (!posl[-S[i]].empty() && posl[-S[i]].front()==i+1))
        {
            ans+=B.Calc(i+2,posr[-S[i]].front()-1);
            B.Add(posr[-S[i]].front(),-1);
            posl[-S[i]].pop();
            posr[-S[i]].pop();
        }
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15