Submission #426958

#	Time	Username	Problem	Language	Result	Execution time	Memory
426958		someone	Wiring (IOI17_wiring)	C++17	13 / 100	1085 ms	16300 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

struct Event {
	bool red;
	ll t;

	bool operator <(const Event& o) const {
		return t < o.t;
	}
};

struct Val {
	ll i, val;

	bool operator <(const Val& o) const {
		return val < o.val;
	}
};

const ll N = 2e5 + 10, INF = 7e12;

vector<Event> e;
ll n, m, t, sum = 0, pre[N], dist[N];

void initDist() {
	ll prec[2] = {-INF, -INF};
	for(int i = 0; i < t; i++) {
		if(e[i].red) {
			pre[i] = prec[1];
			prec[0] = e[i].t;
		} else {
			pre[i] = prec[0];
			prec[1] = e[i].t;
		}
		dist[i] = e[i].t - pre[i];
	}
	prec[0] = INF;
	prec[1] = INF;
	for(int i = t-1; i > -1; i--) {
		if(e[i].red) {
			prec[0] = e[i].t;
			dist[i] = min(dist[i], prec[1] - e[i].t);
		} else {
			prec[1] = e[i].t;
			dist[i] = min(dist[i], prec[0] - e[i].t);
		}
	}
}

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size();
	m = b.size();
	t = n + m;

	for(int i : r)
		e.push_back({true, i});
	for(int i : b)
		e.push_back({false, i});

	sort(e.begin(), e.end());

	initDist();

	set<Val> blue, red;
	for(int i = 0; i < t; i++) {
		if(e[i].red) {
			auto it = blue.begin();
			while(!blue.empty() && (*it).val < e[i].t) {
				sum += (*it).val - e[(*it).i].t;
				blue.erase(it);
				it = blue.begin();
				//cout << "1 " << sum << '\n';
			}
			if(blue.empty()) {
				red.insert({i, 2*e[i].t - pre[i]});
			} else {
				sum += e[i].t - e[(*it).i].t;
				blue.erase(it);
				//cout << "2 " << sum << '\n';
			}
		} else {
			auto it = red.begin();
			while(!red.empty() && (*it).val < e[i].t) {
				sum += (*it).val - e[(*it).i].t;
				red.erase(it);
				it = blue.begin();
				//cout << "3 " << sum << '\n';
			}
			if(red.empty()) {
				blue.insert({i, 2*e[i].t - pre[i]});
			} else {
				sum += e[i].t - e[(*it).i].t;
				red.erase(it);
				//cout << "4 " << sum << '\n';
			}
		}
	}
	for(Val v : red)
		sum += dist[v.i];
	for(Val v : blue)
		sum += dist[v.i];
	return sum;
}

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45