Submission #650202

#	Time	Username	Problem	Language	Result	Execution time	Memory
650202		activedeltorre	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	246 ms	275496 KiB

shoes

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue<int>st[200005];
queue<int>st2[200005];
int fre[200005];
long long aib[200005];
int n;
void update (int poz,int val)
{
    while(poz<=n)
    {
        aib[poz]=aib[poz]+val;
        poz=poz+(poz&(-poz));
    }
}
long long 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)
{
    v.insert(v.begin(),0);
    n=v.size();
    long long suma=0,val,a,b,i;
    for(i=1;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(min(a,b))+querry(max(a,b));
            update(min(a,b),1);
            update(max(a,b),-1);
        }
    }
    return suma;
}
/*int main()
{
    int n,i,j,x;
    cin>>n;
    vector<int>v;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    cout<<count_swaps(v);
}*/

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