oj.uz

Submission #123625

# Submission time Handle Problem Language Result Execution time Memory
123625 2019-07-01T19:43:17 Z egorlifar Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 19316 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;


long long getres(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;
	long long add = 2e18;
	for (int i = 0; i < sz(vx); i++) {
		chkmax(uk, i);
		while (uk + 1 < sz(vx) && getres(i, uk) >= getres(i, uk + 1)) {
			uk++;
		}
		chkmin(add, getres(i, uk));
	}	
	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 10 ms 9752 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 9848 KB Output is correct
7 Correct 11 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 9848 KB Output is correct
11 Correct 10 ms 9876 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 9852 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 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 13040 KB Output is correct
13 Correct 143 ms 19280 KB Output is correct
14 Correct 78 ms 12912 KB Output is correct
15 Correct 77 ms 15460 KB Output is correct
16 Correct 45 ms 12780 KB Output is correct
17 Correct 93 ms 19312 KB Output is correct
18 Correct 82 ms 19316 KB Output is correct
19 Correct 139 ms 19172 KB Output is correct
20 Correct 51 ms 12780 KB Output is correct
21 Correct 94 ms 19308 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 10 ms 9848 KB Output is correct
3 Correct 10 ms 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 9 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 11 ms 9720 KB Output is correct
9 Correct 12 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 12 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 11 ms 9784 KB Output is correct
4 Correct 12 ms 9720 KB Output is correct
5 Correct 10 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 9720 KB Output is correct
9 Correct 14 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 10 ms 9692 KB Output is correct
12 Correct 10 ms 9720 KB Output is correct
13 Correct 10 ms 9720 KB Output is correct
14 Correct 12 ms 9848 KB Output is correct
15 Correct 37 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 14 ms 9848 KB Output is correct
19 Correct 10 ms 9896 KB Output is correct
20 Correct 45 ms 9848 KB Output is correct
21 Correct 21 ms 9848 KB Output is correct
22 Correct 47 ms 9848 KB Output is correct
23 Correct 10 ms 9848 KB Output is correct
24 Correct 48 ms 9848 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 9848 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 9720 KB Output is correct
6 Correct 9 ms 9720 KB Output is correct
7 Correct 9 ms 9720 KB Output is correct
8 Correct 10 ms 9720 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 10 ms 9720 KB Output is correct
14 Correct 12 ms 9720 KB Output is correct
15 Correct 36 ms 9720 KB Output is correct
16 Correct 10 ms 9720 KB Output is correct
17 Correct 11 ms 9820 KB Output is correct
18 Correct 13 ms 9720 KB Output is correct
19 Correct 10 ms 9720 KB Output is correct
20 Correct 44 ms 9848 KB Output is correct
21 Correct 20 ms 9848 KB Output is correct
22 Correct 47 ms 9848 KB Output is correct
23 Correct 10 ms 9720 KB Output is correct
24 Correct 47 ms 9720 KB Output is correct
25 Correct 38 ms 12532 KB Output is correct
26 Correct 349 ms 12720 KB Output is correct
27 Execution timed out 2069 ms 13428 KB Time limit exceeded
28 Halted 0 ms 0 KB -