Submission #143615

#	Time	Username	Problem	Language	Result	Execution time	Memory
143615		JustInCase	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	2 ms	376 KiB

shoes

#include <bits/stdc++.h>

#ifndef LOCAL
	#include "shoes.h"
	#define int32_t int
	#define int64_t long long
#endif

const int32_t MAX_N = 1e5;

struct SegmentTree {
	int32_t treeSize;
	int32_t data[4 * MAX_N + 5], lazy[4 * MAX_N + 5];	

	void init(int32_t _treeSize) {
		treeSize = _treeSize;
	}

	void push_lazy(int32_t node, int32_t low, int32_t high) {
		if(lazy[node] == 0) {
			return;
		}

		data[node] += lazy[node];
		if(low != high) {
			lazy[2 * node] += lazy[node];
			lazy[2 * node + 1] += lazy[node];
		}
		lazy[node] = 0;
	}

	void update(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qHigh, int32_t qVal) {
		push_lazy(node, low, high);

		if(low > qHigh || high < qLow) {
			return;
		}
		else if(low >= qLow && high <= qHigh) {
			lazy[node] += qVal;
			push_lazy(node, low, high);
			return;
		}

		int32_t mid = (low + high) / 2;
		update(2 * node, low, mid, qLow, qHigh, qVal);
		update(2 * node, mid + 1, high, qLow, qHigh, qVal);
	}

	int32_t query(int32_t node, int32_t low, int32_t high, int32_t qInd) {
		push_lazy(node, low, high);

		if(low > qInd || high < qInd) {
			return 0;
		}
		else if(low == qInd && high == qInd) {
			return data[node];
		}

		int32_t mid = (low + high) / 2;
		return std::max(query(2 * node, low, mid, qInd), query(2 * node + 1, mid + 1, high, qInd));
	}
};

SegmentTree segTree;

int64_t count_swaps(std::vector< int32_t > s) {
	int32_t n = s.size();
	
	int64_t ans = 0;

	std::map< int32_t, int32_t > lastOccurance;
	std::vector< int32_t > pairInd(n, -1);
	for(int32_t i = 0; i < n; i++) {
		if(lastOccurance.count(-s[i]) && lastOccurance[-s[i]] != -1) {
			if(s[i] < 0) {
				ans++;
			}
			pairInd[lastOccurance[-s[i]]] = i;
			lastOccurance[-s[i]] = -1;
		}
		else {
			lastOccurance[s[i]] = i;
		}
	}

	segTree.init(n);
	for(int32_t i = 0; i < n; i++) {
		if(pairInd[i] != -1) {
			int32_t ind1 = i + segTree.query(1, 1, n, i + 1);
			int32_t ind2 = pairInd[i] + segTree.query(1, 1, n, pairInd[i]);
			ans += (int64_t) ind2 - ind1 - 1;
			segTree.update(1, 1, n, ind1 + 1, ind2 - 1, 1);
		}
	}

	return ans;
}

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