Submission #384012

#	Time	Username	Problem	Language	Result	Execution time	Memory
384012		BartolM	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	145 ms	33004 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;

int n;
int F[N], bio[N];
set <int> lef[N], rig[N];

void update(int x, int val) {
    for (x++; x<=n; x+=x&-x) F[x]+=val;
}

int query(int x) {
    int ret=0;
    for (x++; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

long long count_swaps(vector<int> v) {
    n=v.size();
    for (int i=0; i<n; ++i) {
        update(i, 1);
        if (v[i]>0) rig[v[i]].insert(i);
        else lef[-v[i]].insert(i);
    }
    ll sol=0;
    for (int i=0; i<n; ++i) {
        if (bio[i]) continue;
        int r, x=abs(v[i]);
        if (v[i]>0) r=*lef[v[i]].begin();
        else r=*rig[-v[i]].begin();
        lef[x].erase(lef[x].begin());
        rig[x].erase(rig[x].begin());
        bio[i]=bio[r]=1;
        sol+=query(r-1)-query(i)+(v[i]>0);
        update(i, -1); update(r, -1);
    }
    return sol;
}

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