Submission #123643

# Submission time Handle Problem Language Result Execution time Memory
123643 2019-07-01T21:35:08 Z egorlifar Palembang Bridges (APIO15_bridge) C++17
22 / 100
173 ms 19224 KB
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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, f1i, f1j, f2i;
int cnti = 0;
int cntj = 0;
long long sumi = 0;
long long sumj = 0;
int cnt1i = 0;
int cnt1j = 0;
long long sum1i = 0;
long long sum1j = 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 delj(int id) {
	if (fj.find({vx[l[id]], id}) != fj.end()) {
		cntj--;
		sumj -= vx[l[id]];
		stj.pb({{vx[l[id]], id}, -1});
		fj.erase({vx[l[id]], id});
	} else {
		if (f1j.find({vx[r[id]], id}) != f1j.end()) {
			stj.pb({{vx[r[id]], id}, -2});
			f1j.erase({vx[r[id]], id});
		} else {
			cnt1j--;
			sum1j -= vx[r[id]];
		}
	}
}


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});
	}
	if (f1i.find({vx[l[id]], id}) != f1i.end()) {
		cnt1i--;
		sum1i -= vx[l[id]];
		//cout << cnt1i << ' ' << sum1i << endl;
		sti.pb({{vx[l[id]], id}, -2});
		f1i.erase({vx[l[id]], id});
	}
	if (f2i.find({vx[r[id]], id}) != f2i.end()) {
		sti.pb({{vx[r[id]], id}, -3});
		f2i.erase({vx[r[id]], id});
	}
}


void updi(int x) {
	//cout << x << endl;
	while (!fi.empty()) {
		auto y = *fi.rbegin();
		if (y.first >= x) {
			fi.erase(y);
			sti.pb({y, -1});
			cnti--;
			sumi -= y.first;
			if (vx[l[y.second]] > x) {
				cnt1i++;
				sum1i += vx[l[y.second]];
				//cout << -x * cnt1i + sum1i << endl;
				f1i.insert({vx[l[y.second]], y.second});
				sti.pb({{vx[l[y.second]], y.second}, 2});
			} else {
				f2i.insert({vx[r[y.second]], y.second});
				sti.pb({{vx[r[y.second]], y.second}, 3});
			}
		} else {
			break;
		}
	}
	//cout << sz(f1i) << ' ' << x << endl;
	while (!f1i.empty()) {
		auto y = *f1i.begin();
		//cout << y.first << ' ' << x << endl;
		if (y.first <= x) {
			f1i.erase(y);
			sti.pb({y, -2});
			cnt1i--;
			sum1i -= y.first;
			//cout << -x * cnt1i + sum1i << endl;
			f2i.insert({vx[r[y.second]], y.second});
			sti.pb({{vx[r[y.second]], y.second}, 3});
		} else {
			break;
		}
	}
	while (!f2i.empty()) {
		auto y = *f2i.begin();
		if (y.first < x) {
			f2i.erase(y);
			sti.pb({y, -3});
			cnti++;
			sumi += y.first;
		} else {
			break;
		}
	}
}

bool was[MAXN];

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;
			if (vx[r[y.second]] < x) {
				cnt1j++;
				sum1j += vx[r[y.second]];
				//cout << r[y.second] << endl;
				//cout << cnt1j << ' ' << r[y.second] << ' ' << x << endl;
			} else {
				f1j.insert({vx[r[y.second]], y.second});
				stj.pb({{vx[r[y.second]], y.second}, 2});
			}
		} else {
			break;
		}
	}
	while (!f1j.empty()) {
		auto y = *f1j.begin();
		if (y.first < x) {
			f1j.erase(y);
			stj.pb({y, -2});
			cnt1j++;
			//cout << cnt1j << ' ' << y.first << ' ' << x << endl;
			sum1j += y.first;
			//cout << cnt1j << endl;
		} else {
			break;
		}
	}
}


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


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



void recalc(int i, int j) {
	i = vx[i];
	j = vx[j];
//	cout << j << endl;
	//cout << st[ft].first << ' ' << vx[l[st[ft].second]] << endl;
	while (ft < sz(st) && (st[ft].first <= i + j || vx[l[st[ft].second]] <= i)) {
		//cout << i << ' ' << j << ' ' << vx[l[st[ft].second]] << endl;
		//if (vx[l[st[ft].second]] < j) {
		if (!was[st[ft].second]) {
			delj(st[ft].second);
			addi(st[ft].second);
		}
		//}
		ft++;
	}
	updi(i);
	updj(j);
	//cout << sum1j << endl;
	//if (i == 2 && j == 5) {
		//cout << getj(5) << endl;
//	}
}




long long getres(int i, int j) {
//	cout << cnti + cntj + cnt1i + cnt1j << endl;
//	cout << -1LL * vx[i] * cnt1i + sum1i << endl;
	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});
		//cout << vx[l[i]] + vx[r[i]] << endl;
		fb[l[i]].pb(i);
	}
	//l - x <= y - r
	//l + r <= x + y;
	sort(all(st));
	for (int i = 0; i < n; i++) {
		where[st[i].second] = i;
		addj(i);
	}
	for (int i = 0; i < sz(vx); i++) {
		for (auto x: fb[i]) {
			delj(x);
			addi(x);
			was[x] = true;
		}
		chkmax(uk, i);
		recalc(i, uk);
		//cout << cnt1i << endl;
		sti.clear();
		stj.clear();
	//	cout << vx[i] << endl;
		while (uk + 1 < sz(vx)) {
			long long cur = getres(i, uk);
			//cout << sz(f1i) << endl;
			int ft1 = ft;
			long long si, sj, ci, cj;
			si = sumi;
			ci = cnti;
			sj = sumj;
			cj = cntj;
			long long s1i, s1j, c1i, c1j;
			s1i = sum1i;
			c1i = cnt1i;
			s1j = sum1j;
			c1j = cnt1j;
			uk++;
			//cout << sz(sti) << endl;
			recalc(i, uk);
			long long cur1 = getres(i, uk);
			//cout << cur << ' ' << cur1 << endl;
			if (cur1 <= cur) {
				sti.clear();
				stj.clear();
				continue;
			}
			//cout << cur << ' ' << cur1 << endl;
			sumi = si;
			cnti = ci;
			cntj = cj;
			sumj = sj;
			sum1i = s1i;
			cnt1i = c1i;
			cnt1j = c1j;
			sum1j = s1j;
			//cout << sum1i - 1LL * vx[i] * cnt1i << ' ' << sum1i << ' ' << cnt1i << endl;
			ft = ft1;
			for (int k = sz(sti) - 1; k >= 0; k--) {
				auto x = sti[k].first;
				int t = sti[k].second;
				if (t == 1 || t == -1) {
					if (t == 1) {
						fi.erase(x);
					} else {
						fi.insert(x);
					}
				} else if (t == 2 || t == -2) {
					if (t == 2) {
						f1i.erase(x);
					} else {
						f1i.insert(x);
					}
				} else {	
					if (t == 3) {
						f2i.erase(x);
					} else {
						f2i.insert(x);
					}
				}
			}		
			//cout << sz(f1i) << endl; 
			sti.clear();
			for (int k = sz(stj) - 1; k >= 0; k--) {
				auto x = stj[k].first;
				int t = stj[k].second;
				if (t == 1 || t == -1) {
					if (t == 1) {
						fj.erase(x);
					} else {
						fj.insert(x);
					}
				} else {
					if (t == 2) {
						f1j.erase(x);
					} else {
						f1j.insert(x);
					}
				}
			}		
			stj.clear();
			uk--;
			break;
		}
		//cout << sz(sti) << endl;
	//	cout << getres(i, uk) << endl;
	//	cout << vx[i] << ' ' << vx[uk] << endl;
		chkmin(add, getres(i, uk));
	}	
	//cout << add << endl;
	cout << ans + 2 * add << '\n';
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 12 ms 9976 KB Output is correct
8 Correct 12 ms 9848 KB Output is correct
9 Correct 11 ms 9848 KB Output is correct
10 Correct 10 ms 9848 KB Output is correct
11 Correct 10 ms 9848 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 11 ms 9848 KB Output is correct
10 Correct 10 ms 9852 KB Output is correct
11 Correct 10 ms 9848 KB Output is correct
12 Correct 40 ms 13036 KB Output is correct
13 Correct 137 ms 19212 KB Output is correct
14 Correct 78 ms 12780 KB Output is correct
15 Correct 79 ms 15264 KB Output is correct
16 Correct 46 ms 12648 KB Output is correct
17 Correct 95 ms 19184 KB Output is correct
18 Correct 83 ms 19224 KB Output is correct
19 Correct 173 ms 19048 KB Output is correct
20 Correct 54 ms 12780 KB Output is correct
21 Correct 103 ms 19184 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 32 ms 9720 KB Output is correct
3 Correct 12 ms 9852 KB Output is correct
4 Incorrect 12 ms 9848 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Incorrect 10 ms 9720 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Incorrect 10 ms 9720 KB Output isn't correct
5 Halted 0 ms 0 KB -