Submission #154132

#	Time	Username	Problem	Language	Result	Execution time	Memory
154132		79brue	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	285 ms	141576 KiB

shoes

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

using namespace std;
typedef long long ll;

int n;
int arr[200002];
int match[200002];
queue<int> matchIdx[200002];
bool chk[200002];

struct fenwick{
    int size;
    ll tree[1000002];

    fenwick(){}
    void reset(int x){
        size = x;
        fill(tree, tree+x+1, 0LL);
    }

    ll getSum(int i){
        ll ans = 0;
        while(i>0){
            ans += tree[i];
            i -= (i&-i);
        }
        return ans;
    }

    ll getSum(int l, int r){
        return getSum(r) - getSum(l-1);
    }

    void update(int i, ll val){
        while(i<=size){
            tree[i] += val;
            i += (i&-i);
        }
    }
} tree;

ll count_swaps(vector<int> _arr) {
    ll ans=0;
    n = (int)_arr.size();
    for(int i=1; i<=n; i++) arr[i] = _arr[i-1];

    tree.reset(n);

    for(int i=1; i<=n; i++){
        tree.update(i, 1);

        if(matchIdx[abs(arr[i])].empty()) matchIdx[abs(arr[i])].push(i);
        else{
            int tmp = matchIdx[abs(arr[i])].front();
            if(arr[tmp] != arr[i]){
                match[tmp] = i;
                match[i] = tmp;
                matchIdx[abs(arr[i])].pop();
            }
            else{
                matchIdx[abs(arr[i])].push(i);
            }
        }
    }

    for(int i=1; i<=n; i++){
        if(chk[match[i]]) continue;
        chk[i] = 1;
        int tmp = match[i];
        ans += tree.getSum(i, tmp) - 2;
        if(arr[i] > 0) ans++;
        tree.update(i, -1);
        tree.update(tmp, -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