oj.uz

Submission #123658

# Submission time Handle Problem Language Result Execution time Memory
123658 2019-07-01T23:04:25 Z egorlifar Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 24040 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 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]];
			} 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];
	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);
			}
		} else {
			break;
		}
	} 
	updi(i);
	updj(j);
}




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

long long getres1(int i, int j) {
	long long add = 0;
	for (int k = 0; k < n; k++) {
		if (l[k] <= i && i <= r[k]) {
			continue;
		}
		if (l[k] <= j && j <= r[k]) {
			continue;
		}
		add += min(min(abs(vx[l[k]] - vx[i]), abs(vx[r[k]] - vx[i])), min(abs(vx[l[k]] - vx[j]), abs(vx[r[k]] - 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 = 4e18;
	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);
				st.erase({vx[l[x]] + vx[r[x]], 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]) {
				if (was[y]) continue;
				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);
					}
				}
			}		
			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;
		}
		chkmin(add, getres(i, uk));
		assert(getres(i, uk) == getres1(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 12 ms 9720 KB Output is correct
2 Correct 10 ms 9592 KB Output is correct
3 Correct 13 ms 9852 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 11 ms 9848 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 11 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 10 ms 9848 KB Output is correct
5 Correct 13 ms 9848 KB Output is correct
6 Correct 12 ms 9848 KB Output is correct
7 Correct 13 ms 9848 KB Output is correct
8 Correct 11 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
12 Correct 40 ms 13300 KB Output is correct
13 Correct 132 ms 19440 KB Output is correct
14 Correct 78 ms 13040 KB Output is correct
15 Correct 79 ms 15608 KB Output is correct
16 Correct 46 ms 12908 KB Output is correct
17 Correct 93 ms 19524 KB Output is correct
18 Correct 82 ms 19516 KB Output is correct
19 Correct 131 ms 19436 KB Output is correct
20 Correct 50 ms 13040 KB Output is correct
21 Correct 95 ms 19440 KB Output is correct

Subtask #3
9.0 / 9.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 13 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 11 ms 9864 KB Output is correct
9 Correct 10 ms 9720 KB Output is correct
10 Correct 11 ms 9740 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 10 ms 9724 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 10 ms 9712 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 9848 KB Output is correct
11 Correct 10 ms 9720 KB Output is correct
12 Correct 10 ms 9848 KB Output is correct
13 Correct 11 ms 9976 KB Output is correct
14 Correct 13 ms 9848 KB Output is correct
15 Correct 22 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 12 ms 9848 KB Output is correct
19 Correct 11 ms 9976 KB Output is correct
20 Correct 24 ms 9976 KB Output is correct
21 Correct 16 ms 9976 KB Output is correct
22 Correct 25 ms 9976 KB Output is correct
23 Correct 12 ms 9976 KB Output is correct
24 Correct 24 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 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 10 ms 9852 KB Output is correct
6 Correct 10 ms 9820 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 9820 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 9820 KB Output is correct
13 Correct 11 ms 9948 KB Output is correct
14 Correct 13 ms 9848 KB Output is correct
15 Correct 22 ms 9976 KB Output is correct
16 Correct 10 ms 9848 KB Output is correct
17 Correct 12 ms 9848 KB Output is correct
18 Correct 12 ms 9848 KB Output is correct
19 Correct 11 ms 9976 KB Output is correct
20 Correct 25 ms 9976 KB Output is correct
21 Correct 17 ms 9976 KB Output is correct
22 Correct 25 ms 9984 KB Output is correct
23 Correct 11 ms 9976 KB Output is correct
24 Correct 25 ms 9976 KB Output is correct
25 Correct 132 ms 24040 KB Output is correct
26 Correct 549 ms 19052 KB Output is correct
27 Execution timed out 2053 ms 23532 KB Time limit exceeded
28 Halted 0 ms 0 KB -