Submission #169907

#	Time	Username	Problem	Language	Result	Execution time	Memory
169907		socho	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	463 ms	23108 KiB

shoes

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

struct node {
	
	int segment_left, segment_right, segment_middle;
	int value;
	node *left, *right;
		
	node(int sle, int sri) {
		// cout << sle << ' ' << sri << endl;
		this->segment_left = sle;
		this->segment_right = sri;
		int mid = (sle + sri) / 2;
		this->segment_middle = mid;
		this->value = 0;
		if (sle == sri) return;
		left = new node(sle, mid);
		right = new node(mid+1, sri);
	}
	
	void update(int pos, int va) {
		if (pos < segment_left) return;
		if (pos > segment_right) return;
		if (pos == segment_left && pos == segment_right) {
			value = va;
			return;
		}
		if (pos <= segment_middle) {
			left->update(pos, va);
		}
		else {
			right->update(pos, va);
		}
		value = left->value + right->value;
	}
	
	int qry(int a, int b) {
		if (b < segment_left || a > segment_right) {
			return 0;
		}
		if (a <= segment_left && b >= segment_right) {
			return value;
		}
		return left->qry(a, b) + right->qry(a, b);
	}
	
} *root;

void setup(int n) {
	root = new node(0, n-1);
}

void update(int ind, int val) {
	root->update(ind, val);
}

int query(int a, int b) {
	return root->qry(a, b);
}

long long count_swaps(vector<int> s) {
	long long need = 0;
	set<pair<int, int> > opn; // value, index
	int n = s.size();
	vector<pair<int, int> > vc;
	for (int i=0; i<n; i++) {
		int wh = s[i];
		int sea = -wh;
		set<pair<int, int> >::iterator x = opn.lower_bound(make_pair(sea, INT_MIN));
		if (x != opn.end() && x->first == sea) {
			int other = x->second;
			vc.push_back(make_pair(other, i));
			opn.erase(x);
		}
		else {
			opn.insert(make_pair(wh, i));
		}
	}
	sort(vc.begin(), vc.end());
	
	setup(n);
	for (int i=0; i<vc.size(); i++) {
		// cout << vc[i].first << ' ' << vc[i].second << endl;
		long long aft = s[vc[i].second];
		long long bef = s[vc[i].first];
		if (aft < bef) {
			// cout << " sw" << endl;
			need++;
		}
		long long dist = vc[i].second - vc[i].first - 1;
		// cout << " > " << dist << endl;
		dist -= query(vc[i].first, vc[i].second);
		// cout << "    : " << dist << endl;
		update(vc[i].first, 1);
		update(vc[i].second, 1);
		need += dist;
	}
	return need;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:84:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<vc.size(); i++) {
                ~^~~~~~~~~~

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