Submission #830505

#	Time	Username	Problem	Language	Result	Execution time	Memory
830505		vnm06	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	55 ms	15632 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

int n;
int tree[200020];

void update(int pos, int st)
{
    while(pos<=n)
    {
        tree[pos]+=st;
        pos+=(pos&(-pos));
    }
}
int query(int pos)
{
    int res=0;
    while(pos)
    {
        res+=tree[pos];
        pos-=(pos&(-pos));
    }
    return res;
}
int query(int le, int ri)
{
    return query(ri)-query(le-1);
}

int otm=100005;
int id[200020];
vector<int> pos[200020];

long long count_swaps(std::vector<int> s)
{
    long long br=0;
    n=s.size();
    for(int i=1; i<=n; i++)
    {
        pos[s[i-1]+otm].push_back(i);
        update(i, 1);
    }
    for(int i=1; i<=n; i++)
    {
        if(!query(i, i)) continue;
        int tch=s[i-1];
        id[tch+otm]++;
        int prch=otm-tch;
        int tpos=pos[prch][id[prch]];
        id[prch]++;
        br+=query(i+1, tpos-1);
        update(tpos, -1);
        if(tch+otm>prch) br++;
    }
	return br;
}

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