Submission #1370146

#TimeUsernameProblemLanguageResultExecution timeMemory
1370146kawhietArranging Shoes (IOI19_shoes)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

vector<int> t;

void update(int id, int tl, int tr, int i, int v) {
	if (tl == tr) {
		t[id] = v;
		return;
	}
	int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
	if (i <= tm) {
		update(x, tl, tm, i, v);
	} else {
		update(y, tm + 1, tr, i, v);
	}
	t[id] = t[x] + t[y];
}

int get(int id, int tl, int tr, int l, int r) {
	if (r < tl || tr < l) return 0;
	if (l <= tl && tr <= r) return t[id];
	int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
	return get(x, tl, tm, l, r) + get(y, tm + 1, tr, l, r);
}

long long count_swaps(vector<int> a) {
	int n = a.size();
	t.resize(4 * n);
	for (int i = 0; i < n; i++) {
		update(0, 0, n - 1, i, 1);
	}
	vector<vector<int>> pos(n + 1);
	for (int i = 0; i < n; i++) {
		pos[abs(a[i])].push_back(i);
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int x = abs(a[i]);
		auto it = upper_bound(pos[x].begin(), pos[x].end(), i);
		if (it == pos[x].end()) {
			continue;
		}
		int j = *it;
		if (a[i] > a[j]) {
			ans++;
		}
		ans += get(0, 0, n - 1, i + 1, j - 1);
		update(0, 0, n - 1, j, 0);
	}
	return ans;
}

int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGkpWAl.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2gRVYT.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status