oj.uz

Submission #143613

# Submission time Handle Problem Language Result Execution time Memory
143613 2019-08-14T18:12:50 Z JustInCase Arranging Shoes (IOI19_shoes) C++17
10 / 100
 3 ms 376 KB 
#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 += ind2 - ind1 - 1;
			segTree.update(1, 1, n, ind1 + 1, ind2 - 1, 1);
		}
	}

	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -