Submission #161725

#	Time	Username	Problem	Language	Result	Execution time	Memory
161725		andrew	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	217 ms	67964 KiB

shoes

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

#define fi first
#define sz(x) (int)x.size()
#define se second
#define pll pair <ll,ll>
#define pii pair <int,int>

using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 2e5;
const ll MAXN = 1123456;

set <ll> v[MAXN];

ll t[N + 2];

void update(ll pos, ll val){
    for(; pos <= N; pos += pos & -pos)t[pos] += val;
}

ll f(ll pos){
    ll res = 0;
    for(; pos > 0; pos -= pos & -pos)res += t[pos];
    return res;
}


ll get(ll l, ll r){
    return f(r) - f(l - 1);
}

long long count_swaps(vector<int> s) {
    ll n = sz(s) / 2, ans = 0;
    vector <int> b = s;

    vector <bool> fl(2 * n + 2);

    for(int i = 0; i < n * 2; i++){
        v[b[i] + N].insert(i);
        update(i + 1, 1);
    }

    for(int i = 0; i < n * 2; i++)if(!fl[i]){
        ll pos = *v[-b[i] + N].begin();
        fl[i] = 1;
        fl[pos] = 1;
        v[b[i] + N].erase(i);
        v[-b[i] + N].erase(pos);
        update(i + 1, -1);
        update(pos + 1, -1);
        ans += f(pos + 1);
        if(b[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