Submission #151507

#	Time	Username	Problem	Language	Result	Execution time	Memory
151507		outsider	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	828 ms	148876 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll int
#define x first
#define y second
using namespace std;
ll n;
vector<ll>a;
vector<ll>fn;
void update(ll x, ll y){
             ll f = x;
            while(f <= n){
               fn[f]+=y;
               f =f|(f+1);
            }
}

ll sum(ll x){
    ll num = 0;
            ll f = x;
        while(f >= 0){
            num += fn[f];
            f=(f&(f+1))-1;
        }

    return num;

}

long long count_swaps(vector<int> s)
{
n=s.size();
a.resize(n+1,1);
fn.resize(n+1);
for (int i=0;i<=n;i++)
    update(i,1);
map<ll,deque<ll> >mp;
for (int i=0;i<n;i++)
    mp[s[i]].push_back(i);
long long ans=0;
 for (ll i=0;i<n;i++)
 {
    if (a[i]==0)
        continue;
  ll p=mp[-s[i]].front();
  mp[-s[i]].pop_front();
  mp[s[i]].pop_front();
  update(p,-1);
  update(i,-1);
  a[i]=a[p]=0;
  ans+=sum(p)-sum(i);
 if (s[i]>0)ans++;
 }
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