Submission #963546

#	Time	Username	Problem	Language	Result	Execution time	Memory
963546		maxFedorchuk	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	177 ms	279632 KiB

shoes

#include <bits/stdc++.h>

#include "shoes.h"

using namespace std;

const long long MX=2e5+5;

queue < long long > st[2*MX];
long long fen[2*MX],a[2*MX];

long long n;

void upd(long long in,long long zn)
{
    while(in<=n)
    {
        fen[in]+=zn;
        in|=(in+1);
    }
}

long long fget(long long in)
{
    long long rt=0;
    while(in>0)
    {
        rt+=fen[in];
        in=(in&(in+1))-1;
    }
    return rt;
}

long long count_swaps(vector<int> s) 
{
    n=s.size();

    for(long long i=0;i<n;i++)
    {
        a[i+1]=s[i];
    }

    for(long long i=1;i<=n;i++)
    {
        upd(i,1);
    }

    long long ans=0;
    for(long long i=1;i<=n;i++)
    {
        if(!st[MX-a[i]].empty())
        {
            long long l=st[MX-a[i]].front();
            st[MX-a[i]].pop();

            ans+=fget(i)-fget(l)-(a[i]>0);

            upd(i,-1);
            upd(l,1);
        }
        else
        {
            st[MX+a[i]].push(i);
        }
    }

    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