Submission #842578

#	Time	Username	Problem	Language	Result	Execution time	Memory
842578		beepbeepsheep	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	114 ms	141312 KiB

shoes

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

#define ll long long
const ll maxn=2e5+5;
ll fen[maxn];
bool vis[maxn];
void upd(ll x){
    if (x==0) return;
    while (x<maxn){
        fen[x]++;
        x+=(x&-x);
    }
}
ll query(ll x){
    ll ans=0;
    while (x){
        ans+=fen[x];
        x-=(x&-x);
    }
    return ans;
}
ll query(ll x, ll y){
    return query(y)-query(x-1);
}
queue<ll> adj[maxn];
ll n;
long long count_swaps(std::vector<int> v){
    n=v.size();
    for (int i=0;i<n;i++){
        adj[v[i]+100000].emplace(i);
    }
    ll ans=0;
    for (int i=0;i<n;i++){
        if (vis[i]) continue;
        ll ele=v[i];
        ll inv=-v[i];
        ll pos=adj[inv+100000].front();
        adj[inv+100000].pop();
        adj[ele+100000].pop();
        ans+=(pos-i-1)-query(i+1,pos);
        ans+=(ele>inv);
        upd(i),upd(pos);
        vis[i]=vis[pos]=1;
    }
	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