Submission #123632

#	Time	Username	Problem	Language	Result	Execution time	Memory
123632		egorlifar	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	140 ms	19244 KiB

bridge

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 200228;


int n, k;
int l[MAXN], r[MAXN];
vector<int> fb[MAXN];
vector<int> fe[MAXN];
long long score[MAXN];
vector<int> vx;
int where[MAXN];
vector<pair<int, int> > st;
int ft = 0;
set<pair<int, int> > fi, fj;
int cnti = 0;
int cntj = 0;
long long sumi = 0;
long long sumj = 0;
vector<pair<pair<int, int>, int> > sti, stj;


void addi(int id) {
	fi.insert({vx[r[id]], id});
	sti.pb({{vx[r[id]], id}, 1});
	sumi += vx[r[id]];
	cnti++;
}


void addj(int id) {
	fj.insert({vx[l[id]], id});
	stj.pb({{vx[l[id]], id}, 1});
	sumj += vx[l[id]];
	cntj++;
}


void deli(int id) {
	if (fi.find({vx[r[id]], id}) != fi.end()) {
		cnti--;
		sumi -= vx[r[id]];
		sti.pb({{vx[r[id]], id}, -1});
		fi.erase({vx[r[id]], id});
	}
}


void updi(int x) {
	while (!fi.empty()) {
		auto y = *fi.rbegin();
		if (y.first >= x) {
			fi.erase(y);
			sti.pb({y, -1});
			cnti--;
			sumi -= y.first;
		} else {
			break;
		}
	}
}


void updj(int x) {
	while (!fj.empty()) {
		auto y = *fj.begin();
		if (y.first <= x) {
			fj.erase(y);
			stj.pb({y, -1});
			cntj--;
			sumj -= y.first;
		} else {
			break;
		}
	}
}



void recalc(int i, int j) {
	i = vx[i];
	j = vx[j];
	while (ft < sz(st) && st[ft].first < i + j) {
		deli(st[ft].second);
		addj(st[ft].second);
		ft++;
	}
	updi(i);
	updj(j);
}


long long geti(int x) {
	return 1LL * x * cnti - sumi;
}


long long getj(int x) {
	return -1LL * x * cntj + sumj;
}


long long getres(int i, int j) {
	long long add = geti(vx[i]) + getj(vx[j]);
	return add;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> k >> n;
	long long ans = 0;
	int uk = 0;
	for (int i = 0; i < n; i++) {
		char c, c1;
		int x, x1;
		cin >> c >> x >> c1 >> x1;
		if (c == c1) {
			ans += abs(x1 - x);
			continue;
		}
		if (x > x1) {
			swap(x, x1);
		}
		ans += x1 - x + 1;
		l[uk] = x;
		r[uk] = x1;
		uk++;
	}
	n = uk;
	for (int i = 0; i < n; i++) {
		vx.pb(l[i]);
		vx.pb(r[i]);
	}
	vx.pb(0);
	sort(all(vx));
	vx.resize(distance(vx.begin(), unique(all(vx))));
	for (int i = 0; i < n; i++) {
		l[i] = lower_bound(all(vx), l[i]) - vx.begin();
		r[i] = lower_bound(all(vx), r[i]) - vx.begin();
	}
	if (k == 1) {
		for (int i = 0; i < n; i++) {
			fb[l[i]].pb(i);
			fe[r[i]].pb(i);
			//cout << l[i] << ' ' << r[i] << endl;
		}
		long long sum = 0;
		int cnt = 0;
		for (int i = 0; i < sz(vx); i++) {
			for (auto x: fe[i]) {
				sum += vx[r[x]];
				cnt++;
			}
			score[i] += 1LL * vx[i] * cnt - sum;
		}	
		cnt = 0;
		sum = 0;
		long long add = 2e18;
		for (int i = sz(vx) - 1; i >= 0; i--) {
			for (auto x: fb[i]) {
				sum += vx[l[x]];
				cnt++;
			}
			score[i] += -1LL * vx[i] * cnt + sum;
			chkmin(add, score[i]);
		}	
		//cout << add << endl;
		cout << ans + 2 * add << '\n';
		return 0;
	}
	uk = 0;
	ft = 0;
	long long add = 2e18;
	for (int i = 0; i < n; i++) {
		//x - r[i] <= l[i] - y
		//x + y <= l[i] + r[i]
		st.pb({vx[l[i]] + vx[r[i]], i});
	}
	sort(all(st));
	for (int i = 0; i < n; i++) {
		where[st[i].second] = i;
		addi(i);
	}
	for (int i = 0; i < sz(vx); i++) {
		chkmax(uk, i);
		recalc(i, uk);
		while (uk + 1 < sz(vx)) {
			long long cur = getres(i, uk);
			uk++;
			int ft1 = ft;
			long long si, sj, ci, cj;
			si = sumi;
			ci = cnti;
			sj = sumj;
			cj = cntj;
			recalc(i, uk);
			long long cur1 = getres(i, uk);
			if (cur1 <= cur) {
				continue;
			}
			sumi = si;
			cnti = ci;
			cntj = cj;
			sumj = sj;
			ft = ft1;
			for (int k = sz(sti) - 1; k >= 0; k--) {
				auto x = sti[k].first;
				int t = sti[k].second;
				if (t == 1) {
					fi.erase(x);
				} else {
					fi.insert(x);
				}
			}		
			sti.clear();
			for (int k = sz(stj) - 1; k >= 0; k--) {
				auto x = stj[k].first;
				int t = stj[k].second;
				if (t == 1) {
					fj.erase(x);
				} else {
					fj.insert(x);
				}
			}		
			stj.clear();
			break;
		}
		chkmin(add, getres(i, uk));
	}	
	cout << ans + 2 * add << '\n';
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37