Submission #143558

#	Time	Username	Problem	Language	Result	Execution time	Memory
143558		abeker	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	282 ms	35704 KiB

shoes

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

typedef long long ll;

const int MAXN = 2e5 + 5;

struct fenwick {
	vector <int> fen;
	fenwick(int n) {
		fen.resize(n + 5);
	}
	void update(int x, int val) {
		for (x++; x < fen.size(); x += x & -x)
			fen[x] += val;
	}
	int get(int x) {
		int res = 0;
		for (x++; x; x -= x & -x)
			res += fen[x];
		return res;
	}
};

int N;
vector <int> lft[MAXN], rig[MAXN];
vector <int> perm[MAXN], pos[MAXN];
	
ll inversions(vector <int> v) {
	reverse(v.begin(), v.end());
	fenwick tmp(v.size());
	ll res = 0;
	for (auto it : v) {
		res += tmp.get(it);
		tmp.update(it, 1);
	}
	return res;
}

ll count_swaps(vector <int> shoes) {
	N = shoes.size();
	vector <int> todo(N, -1);
	for (int i = 0; i < N; i++) {
		int sz = abs(shoes[i]);
		if (shoes[i] < 0) {
			perm[sz].push_back(2 * lft[sz].size());					
			lft[sz].push_back(i);
		}
		else {
			perm[sz].push_back(2 * rig[sz].size() + 1);
			rig[sz].push_back(i);
		}
		pos[sz].push_back(i);
	}
	
	ll sol = 0;
	for (int i = 0; i < N; i++) {
		sol += inversions(perm[i]);
		for (int j = 0; j < lft[i].size(); j++) 
			todo[max(lft[i][j], rig[i][j])] = min(lft[i][j], rig[i][j]);
	}
	
	fenwick fin(N);
	for (int i = 0; i < N; i++) 
		if (todo[i] != -1) {
			sol += fin.get(N) - fin.get(todo[i]);
			fin.update(todo[i], 1);
			fin.update(i, 1);
		}
	
	fenwick sub(N);	
	for (int i = 0; i < N; i++) {
		for (auto it : pos[i])
			if (todo[it] != -1) {
				sol -= sub.get(N) - sub.get(todo[it]);
				sub.update(todo[it], 1);
				sub.update(it, 1);
			}
		for (auto it : pos[i])
			if (todo[it] != -1) {
				sub.update(todo[it], -1);
				sub.update(it, -1);
			}
	}
	
	return sol;
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwick::update(int, int)':
shoes.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (x++; x < fen.size(); x += x & -x)
             ~~^~~~~~~~~~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lft[i].size(); j++) 
                   ~~^~~~~~~~~~~~~~~

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