Submission #615511

#	Time	Username	Problem	Language	Result	Execution time	Memory
615511		Mohammed_Atalah	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	178 ms	34156 KiB

shoes

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

struct segtree {

	int size = 1;
	vector<int> sums;

	void init(int n) {
		while (size < n) {
			size *= 2;
		}
		sums.assign(2 * size, 0);
	}

	void build(vector<int> &v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			if (lx  < v.size()) {
				sums[x] = v[lx];
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(v, 2 * x + 1, lx, m);
		build(v, 2 * x + 2, m, rx);
		sums[x] = sums[2 * x + 2] + sums[2 * x + 1];
	}

	void build(vector<int> &v) {
		build(v, 0, 0, size);
	}

	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			sums[x] = v;
			return;
		}

		int m = (lx + rx) / 2;

		if (i < m) {
			set(i, v, x * 2 + 1, lx, m);
		} else {
			set(i, v, x * 2 + 2, m, rx);
		}

		sums[x] = sums[x * 2 + 1] + sums[x * 2 + 2];
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}


	int sum (int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx )return 0 ;
		if (l <= lx && rx <= r) return sums[x];
		int m = (rx + lx) / 2;
		int n1 = sum(l, r, x * 2 + 1, lx, m );
		int n2 = sum(l, r, x * 2 + 2, m, rx );
		return n1 + n2;

	}

	int sum(int l, int r) {
		return sum(l, r, 0, 0, size);
	}

};


long long count_swaps(std::vector<int> s) {
	int n = s.size();
	vector<set<int>> left(n + 1);
	vector<set<int>> right(n + 1);
	vector<int> vis(n);
	for (int i = 0; i < n ; i++) {
		if (s[i] < 0) {
			left[abs(s[i])].insert(i);
		} else {
			right[abs(s[i])].insert(i);
		}
	}
	segtree st;
	st.init(n);
	long long result = 0;

	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		if (s[i] < 0) {
			auto it  = right[abs(s[i])].lower_bound(i);
			result += *it - i;
			result--;
			result -= st.sum(i, *it);
			st.set(*it, 1);
			vis[*it] = 1;
			right[abs(s[i])].erase(it);
		} else {
			auto it  = left[abs(s[i])].lower_bound(i);
			result += *it - i;

			result -= st.sum(i, *it);
			st.set(*it, 1);
			vis[*it] = 1;
			left[abs(s[i])].erase(it);
		}
	}


	return result;
}

Compilation message (stderr)

shoes.cpp: In member function 'void segtree::build(std::vector<int>&, int, int, int)':
shoes.cpp:19:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    if (lx  < v.size()) {
      |        ~~~~^~~~~~~~~~

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