Submission #145285

#	Time	Username	Problem	Language	Result	Execution time	Memory
145285		JovanK26	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	436 ms	25976 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int bit[200001];
void update(int x,int n,int val)
{
    x++;
    while(x<=n)
    {
        bit[x]+=val;
        x+=(x&(-x));
    }
}
int query(int x)
{
    int rez=0;
    x++;
    while(x>0)
    {
        rez+=bit[x];
        x-=(x&(-x));
    }
    return rez;
}
map<int,vector<int> >mp;
long long count_swaps(vector<int> s)
{
    long long rez=0;
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        update(i,n,1);
    }
    for(int i=n-1;i>=0;i--)
    {
        mp[s[i]].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        if(query(i)-query(i-1)!=1)continue;
        int j=mp[-s[i]].back();
        mp[s[i]].pop_back();
        mp[-s[i]].pop_back();
        update(i,n,-1);
        update(j,n,-1);
        rez+=query(j)-query(i)+(s[i]>0);
    }
    return rez;
}

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