oj.uz

Submission #123641

# Submission time Handle Problem Language Result Execution time Memory
123641 2019-07-01T21:33:10 Z egorlifar Palembang Bridges (APIO15_bridge) C++17
63 / 100
 574 ms 27484 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;
		}
	}
}


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) {
		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;
	}
	//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++) {
		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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 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 11 ms 9848 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 10 ms 9848 KB Output is correct
10 Correct 10 ms 9848 KB Output is correct
11 Correct 10 ms 9848 KB Output is correct

Subtask #2
14.0 / 14.0

# 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 Correct 11 ms 9848 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 10 ms 9848 KB Output is correct
10 Correct 12 ms 9848 KB Output is correct
11 Correct 11 ms 9848 KB Output is correct
12 Correct 43 ms 13676 KB Output is correct
13 Correct 130 ms 21520 KB Output is correct
14 Correct 78 ms 13936 KB Output is correct
15 Correct 77 ms 16628 KB Output is correct
16 Correct 46 ms 14208 KB Output is correct
17 Correct 98 ms 21580 KB Output is correct
18 Correct 82 ms 21088 KB Output is correct
19 Correct 138 ms 21460 KB Output is correct
20 Correct 55 ms 14572 KB Output is correct
21 Correct 94 ms 21200 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9712 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 10 ms 9720 KB Output is correct
4 Correct 12 ms 9800 KB Output is correct
5 Correct 12 ms 9720 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 12 ms 9720 KB Output is correct
10 Correct 12 ms 9720 KB Output is correct
11 Correct 12 ms 9852 KB Output is correct
12 Correct 10 ms 9720 KB Output is correct

Subtask #4
32.0 / 32.0

# 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 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 9720 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 10 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 10 ms 9720 KB Output is correct
12 Correct 10 ms 9720 KB Output is correct
13 Correct 11 ms 9976 KB Output is correct
14 Correct 13 ms 9848 KB Output is correct
15 Correct 12 ms 9848 KB Output is correct
16 Correct 10 ms 9848 KB Output is correct
17 Correct 11 ms 9848 KB Output is correct
18 Correct 11 ms 9848 KB Output is correct
19 Correct 11 ms 9976 KB Output is correct
20 Correct 12 ms 9848 KB Output is correct
21 Correct 11 ms 9848 KB Output is correct
22 Correct 12 ms 9848 KB Output is correct
23 Correct 12 ms 9976 KB Output is correct
24 Correct 12 ms 9848 KB Output is correct

Subtask #5
0 / 37.0

# 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 9720 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 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 10 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 10 ms 9720 KB Output is correct
12 Correct 10 ms 9860 KB Output is correct
13 Correct 11 ms 9976 KB Output is correct
14 Correct 12 ms 9848 KB Output is correct
15 Correct 12 ms 9848 KB Output is correct
16 Correct 10 ms 9848 KB Output is correct
17 Correct 11 ms 9852 KB Output is correct
18 Correct 11 ms 9976 KB Output is correct
19 Correct 11 ms 9976 KB Output is correct
20 Correct 12 ms 9848 KB Output is correct
21 Correct 12 ms 9848 KB Output is correct
22 Correct 12 ms 9848 KB Output is correct
23 Correct 11 ms 9976 KB Output is correct
24 Correct 12 ms 9848 KB Output is correct
25 Correct 141 ms 24632 KB Output is correct
26 Correct 427 ms 19664 KB Output is correct
27 Correct 574 ms 20196 KB Output is correct
28 Correct 522 ms 20884 KB Output is correct
29 Correct 450 ms 20712 KB Output is correct
30 Correct 219 ms 15720 KB Output is correct
31 Correct 163 ms 27484 KB Output is correct
32 Correct 266 ms 20712 KB Output is correct
33 Correct 250 ms 20444 KB Output is correct
34 Correct 305 ms 20640 KB Output is correct
35 Correct 198 ms 25312 KB Output is correct
36 Correct 246 ms 22072 KB Output is correct
37 Incorrect 171 ms 26852 KB Output isn't correct