Submission #1241011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241011		nvujica	Wiring (IOI17_wiring)	C++20	100 / 100	356 ms	18300 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 2e5 + 10, off = (1 << 18);
const ll inf = (1LL << 60);

ll tour[2][2 * off];
ll prop[2][2 * off];
ll dp[maxn];
vector <pair<int, int> > v;
vector <int> poc;

void push(bool f, int x){
	if(x >= off) return;

	ll val = prop[f][x];
	prop[f][x] = 0;

	tour[f][x * 2] += val;
	prop[f][x * 2] += val;

	tour[f][x * 2 + 1] += val;
	prop[f][x * 2 + 1] += val;
}

void update(bool f, int x, int lo, int hi, int l, int r, ll val){
	if(r <= l) return;
	
	push(f, x);

	if(hi <= l || r <= lo) return;

	if(l <= lo && hi <= r){
		tour[f][x] += val;
		prop[f][x] += val;
		return;
	}

	int mid = (lo + hi) / 2;
	update(f, x * 2, lo, mid, l, r, val);
	update(f, x * 2 + 1, mid, hi, l, r, val);
	tour[f][x] = min(tour[f][x * 2], tour[f][x * 2 + 1]);
}

ll query(bool f, int x, int lo, int hi, int l, int r){
	if(r <= l) return inf;
	
	push(f, x);

	if(hi <= l || r <= lo) return inf;

	if(l <= lo && hi <= r){
		return tour[f][x];
	}

	int mid = (lo + hi) / 2;
	return min(query(f, x * 2, lo, mid, l, r), query(f, x * 2 + 1, mid, hi, l, r));
}

ll min_total_length(vector<int> r, vector<int> b) {
	for(int i = 0; i < r.size(); i++){
		v.push_back({r[i], 0});
	}

	for(int i = 0; i < b.size(); i++){
		v.push_back({b[i], 1});
	}

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

	poc.push_back(0);

	for(int i = 0; i < v.size(); i++){
//		cout << v[i].fi << ' ' << v[i].se << endl;
		if(!i || v[i].se != v[i - 1].se){
//			cout << "sad " << i << endl;
			poc.push_back(i);
		}
	}
	
//	cout << poc.size() << endl;

	poc.push_back(v.size());
	
//	for(int i = 0; i < poc.size(); i++){
//		cout << poc[i] << ' ';
//	}
//	cout << endl;
	
	int p = 0;

	for(int i = 0; i < v.size(); i++){
		int x = v[i].fi;
		int c = v[i].se;
		
//		cout << "x c: " << x << ' ' << c << endl;
		
		while(poc[p + 1] <= i) p++;

		int l = poc[p - 1], r = poc[p], nxt = poc[p + 1];
		
//		cout << "l r nxt: " << l << ' ' << r << ' ' << nxt << endl;

		// if(i == r) update(0, 1, 0, off, l)

		if(r - (i - r) > l){
			update(c, 1, 0, off, l, r - (i - r), x - v[r].fi);
//			cout << "update1 " << c << ' ' << l << ' ' << r - (i - r) << ' ' << x - v[r].fi << endl;
		}
		
		if(r){
			update(c, 1, 0, off, r - (i - r), r, x - v[r - 1].fi);
//			cout << "update2 " << c << ' ' << r - (i - r) << ' ' << r << ' ' << x - v[r - 1].fi << endl;
		}
	

		dp[i] = query(c, 1, 0, off, l, r);
//		cout << "dp: " << i << ' ' << dp[i] << endl;
		
		if(nxt != i + 1) update(!c, 1, 0, off, i + 1, i + 2, dp[i]);
		else{
			if(r == i){
				ll q = query(!c, 1, 0, off, i, i + 1);
//				if(i == 0) cout << q << ' ' << dp[i] << endl;
				
				if(dp[i] < q) update(!c, 1, 0, off, i, i + 1, dp[i] - q);
			}
			update(c, 1, 0, off, i + 1, i + 2, dp[i]);
//			cout << "update3 " << c << ' ' << i + 1 << ' ' << i + 2 << ' ' << dp[i] << endl;
		}

		update(!c, 1, 0, off, r, i + 1, v[nxt].fi - x);
//		cout << "update4 " << c << ' ' << r << ' ' << i + 1 << ' ' << v[nxt].fi - x << endl;
	}

	ll ans = dp[v.size() - 1];
	
	return ans;
}

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