Submission #650198

#	Time	Username	Problem	Language	Result	Execution time	Memory
650198		activedeltorre	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1062 ms	269520 KiB

shoes

#include <vector>
#include <queue>
using namespace std;
queue<int>st[200005];
queue<int>st2[200005];
int fre[200005];
int aib[200005];
int n;
void update (int poz,int val)
{
    while(poz<=n)
    {
        aib[poz]=aib[poz]+val;
        poz=poz+(poz&(-poz));
    }
}
int querry (int poz)
{
    long long suma=0;
    while(poz>0)
    {
        suma=suma+aib[poz];
        poz=poz-(poz&(-poz));
    }
    return suma;
}
long long count_swaps(vector<int>v)
{
    n=v.size();
    long long suma=0,val,a,b,i;
    for(i=0;i<n;i++)
    {
        if(v[i]<0)
        {
            st[-v[i]].push(i);
        }
        else
        {
            st2[v[i]].push(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(fre[i]==0)
        {
            val=max(v[i],-v[i]);
            a=st[val].front();
            b=st2[val].front();
            if(b<a)
            {
                suma++;
            }
            fre[a]=1;
            fre[b]=1;
            st[val].pop();
            st2[val].pop();
            suma=suma+max(a,b)-min(a,b)-1;
            suma=suma-querry(max(a,b))-querry(min(a,b));
            update(min(a,b),1);
            update(max(a,b),-1);
        }
    }
    return suma;
}

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