Submission #1215807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215807		Szil	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1097 ms	14484 KiB

shoes

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

using namespace std;

struct segtree {
    vector<int> tree;
    int n;

    segtree(int n) : n(n) {
        tree.resize(2*n);
    }

    void upd(int u, int k) {
        tree[u += n] += k;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = tree[2*u] + tree[2*u+1];
        }
    }

    int qry(int l, int r) {
        int res = 0;
        l += n; r += n;
        while (l <= r) {
            if (l % 2 == 1) res += tree[l++];
            if (r % 2 == 0) res += tree[r--];
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;
    vector<int> v = s;
    for (int &i : v) cin >> i;
    
	vector<int> goal;
    map<int, int> cnt;
	for (int i = 0; i < 2*n; i++) {
        int x = v[i];
		if (cnt[x] > 0) cnt[x]--;
		else {
            goal.emplace_back(-abs(x));
            goal.emplace_back(abs(x));
            cnt[-x]++;
        }
	}

	vector<bool> done(2*n);
    long long ans = 0;
    segtree st(2*n+1);
	for (int i = 0; i < 2*n; i++) {
		int j = 0;
		for (; j < 2*n; j++) {
			if (!done[j] && goal[j] == v[i]) {
				break;
			}
		}
		done[j] = 1;
		ans += st.qry(j, 2*n);
        st.upd(j, 1);
	}

    return ans;
}

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