Submission #143642

#	Time	Username	Problem	Language	Result	Execution time	Memory
143642		JustInCase	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	867 ms	150952 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 = 2e5;

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 + 1, 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, std::queue< int32_t > > lastOccurance;
	std::vector< int32_t > pairInd(n, -1);
	for(int32_t i = 0; i < n; i++) {
		if(!lastOccurance[-s[i]].empty()) {
			if(s[i] < 0) {
				ans++;
			}
			pairInd[lastOccurance[-s[i]].front()] = i;
			lastOccurance[-s[i]].pop();
		}
		else {
			lastOccurance[s[i]].push(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] + 1);
			
			ans += (int64_t) ind2 - ind1 - 1;
			segTree.update(1, 1, n, i + 1, pairInd[i] + 1, 1);
		}
	}

	return ans;
}

#ifdef LOCAL
int main() {
	int32_t n;
	std::cin >> n;

	std::vector< int32_t > v(2 * n);
	for(int32_t i = 0; i < 2 * n; i++) {
		std::cin >> v[i];
	}

	std::cout << count_swaps(v) << '\n';
}
#endif

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