Submission #768013

#	Time	Username	Problem	Language	Result	Execution time	Memory
768013		Alma	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	106 ms	17920 KiB

shoes

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

vector<int> segTree;
vector<pair<int, int>> pairs;
unordered_map<int, set<int>> pos;

void update(int n, int l, int r, int x, int v) {
    if (l == r) {
        segTree[n] += v;
        return;
    }
    int m = (l+r) / 2;
    if (x <= m) update(2*n, l, m, x, v);
    else update(2*n+1, m+1, r, x, v);
    
    segTree[n] = segTree[2*n] + segTree[2*n+1];
}

int query(int n, int l, int r, int lb, int rb) {
    if (rb < l or r < lb) {
        return 0;
    } 
    if (lb <= l and r <= rb) {
        return segTree[n];
    }
    int m = (l+r) / 2;
    int s1 = query(2*n, l, m, lb, rb);
    int s2 = query(2*n+1, m+1, r, lb, rb);
    return s1 + s2;
}

long long count_swaps(vector<int> s) {

    int n = s.size();
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int x = s[i];

        if (pos.find(-x) != pos.end()) {
            ans += i - *pos[-x].begin() - 1;
            if (x < 0) ans++;

            pairs.push_back({*pos[-x].begin(), i});
            pos[-x].erase(pos[-x].begin());
            if ((int)pos[-x].size() == 0) pos.erase(-x);
        } 
        else {
            pos[x].insert(i);
        }
    }

    sort(pairs.begin(), pairs.end());
    segTree = vector<int>(4*n, 0);

    for (pair<int, int> p: pairs) {
        ans -= query(1, 0, n-1, p.first, p.second);
        update(1, 0, n-1, p.first, -1);
        update(1, 0, n-1, p.second, 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