oj.uz

Submission #123646

# Submission time Handle Problem Language Result Execution time Memory
123646 2019-07-01T21:42:15 Z egorlifar Palembang Bridges (APIO15_bridge) C++17
63 / 100
 645 ms 28376 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];
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;
}
vector<int> fs;
set<pair<int, int> > st;
vector<pair<int, int> > gg;

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 (!st.empty()) {	
		auto x = *st.begin();
		if (x.first <= i + j) {
			st.erase(x);
			gg.pb(x);
			if (!was[x.second]) {
				delj(x.second);
				addi(x.second);
				was[x.second] = true;
				fs.pb(x.second);
			}
			//}
			ft++;
		} else {
			break;
		}
	} 
	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]
		//cout << vx[l[i]] + vx[r[i]] << endl;
		fb[l[i]].pb(i);
		fe[r[i]].pb(i);
	}
	//l - x <= y - r
	//l + r <= x + y;
	for (int i = 0; i < n; i++) {
		addj(i);
	}
	for (int i = 0; i < sz(vx); i++) {
		for (auto x: fb[i]) {
			if (!was[x]) {
				delj(x);
				addi(x);
				was[x] = true;
			}
		}
		chkmax(uk, i);
		recalc(i, uk);
		//cout << cnt1i << endl;
		sti.clear();
		stj.clear();
		fs.clear();
		gg.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;
			vector<pair<int, int> > ff;
			for (auto y: fe[uk]) {
				st.insert({vx[l[y]] + vx[r[y]], y});
				ff.pb({vx[l[y]] + vx[r[y]], y});
			}
			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();
				fs.clear();
				gg.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();
			for (auto y: fs) {
				was[y] = false;
			}
			for (auto y: gg) {
				st.insert(y);
			}
			for (auto y: ff) {
				st.erase(y);
			}
			fs.clear();
			gg.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 11 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 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 10 ms 9848 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 11 ms 9948 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 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 9808 KB Output is correct
8 Correct 10 ms 9852 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
12 Correct 42 ms 12908 KB Output is correct
13 Correct 162 ms 19208 KB Output is correct
14 Correct 78 ms 12784 KB Output is correct
15 Correct 77 ms 15348 KB Output is correct
16 Correct 45 ms 12656 KB Output is correct
17 Correct 92 ms 19180 KB Output is correct
18 Correct 81 ms 19292 KB Output is correct
19 Correct 127 ms 19024 KB Output is correct
20 Correct 51 ms 12656 KB Output is correct
21 Correct 92 ms 19184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 10 ms 9848 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 9 ms 9720 KB Output is correct
8 Correct 9 ms 9720 KB Output is correct
9 Correct 10 ms 9720 KB Output is correct
10 Correct 10 ms 9848 KB Output is correct
11 Correct 10 ms 9848 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 9 ms 9720 KB Output is correct
3 Correct 9 ms 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 10 ms 9804 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 10 ms 9852 KB Output is correct
8 Correct 9 ms 9848 KB Output is correct
9 Correct 10 ms 9848 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 9852 KB Output is correct
13 Correct 10 ms 9976 KB Output is correct
14 Correct 15 ms 9848 KB Output is correct
15 Correct 14 ms 9976 KB Output is correct
16 Correct 10 ms 9848 KB Output is correct
17 Correct 11 ms 9848 KB Output is correct
18 Correct 10 ms 9848 KB Output is correct
19 Correct 10 ms 9976 KB Output is correct
20 Correct 12 ms 9976 KB Output is correct
21 Correct 11 ms 9976 KB Output is correct
22 Correct 11 ms 9976 KB Output is correct
23 Correct 11 ms 9848 KB Output is correct
24 Correct 12 ms 9976 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 9724 KB Output is correct
5 Correct 9 ms 9848 KB Output is correct
6 Correct 9 ms 9720 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 10 ms 9720 KB Output is correct
9 Correct 10 ms 9804 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 9976 KB Output is correct
16 Correct 10 ms 9852 KB Output is correct
17 Correct 11 ms 9848 KB Output is correct
18 Correct 10 ms 9848 KB Output is correct
19 Correct 11 ms 9976 KB Output is correct
20 Correct 12 ms 9976 KB Output is correct
21 Correct 11 ms 9976 KB Output is correct
22 Correct 12 ms 9976 KB Output is correct
23 Correct 12 ms 9848 KB Output is correct
24 Correct 12 ms 9976 KB Output is correct
25 Correct 139 ms 23724 KB Output is correct
26 Correct 504 ms 18540 KB Output is correct
27 Correct 600 ms 23332 KB Output is correct
28 Correct 642 ms 23616 KB Output is correct
29 Correct 645 ms 23808 KB Output is correct
30 Correct 312 ms 17008 KB Output is correct
31 Correct 171 ms 25696 KB Output is correct
32 Correct 395 ms 23696 KB Output is correct
33 Correct 286 ms 23660 KB Output is correct
34 Correct 517 ms 23516 KB Output is correct
35 Correct 248 ms 24800 KB Output is correct
36 Correct 359 ms 25316 KB Output is correct
37 Incorrect 228 ms 28376 KB Output isn't correct