Submission #143553

#	Time	Username	Problem	Language	Result	Execution time	Memory
143553		muradeyn	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	786 ms	146936 KiB

shoes

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

using namespace std;

const int maxx = 200001;

int fen[maxx];

void update(int idx) {
    idx++;
    while (idx < maxx)fen[idx]++ , idx += (idx & -idx);
}

int get(int idx) {
    int ret = 0;
    while (idx > 0) {
        ret += fen[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

int query(int l , int r) {
    l++; r++;
    if (l > r)return 0;
    return get(r) - get(l - 1);
}

map< int , queue<int> >mp;

long long count_swaps(vector<int> s) {
	long long ret = 0;
	int n = s.size();
	for (int i = 0;i<n;i++)mp[s[i]].push(i);
	for (int i = 0;i<n;i++) {
        if (mp[s[i]].front() == i) {
            int nxt = mp[-s[i]].front();
            mp[s[i]].pop();
            mp[-s[i]].pop();
            ret += (nxt - i - 1) - query(i + 1 , nxt - 1);
            update(nxt);
            update(i);
            if (s[i] >= 0)ret++;
        }
	}
	return ret;
}

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