oj.uz

Submission #264840

# Submission time Handle Problem Language Result Execution time Memory
264840 2020-08-14T10:25:41 Z Berted Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 16408 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#define vi vector<int>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long
using namespace std;

const int INF = 1e9;
const ll INF2 = 1e18;

int C2[200001], C2sz = 0;

struct BIT
{
	ll fwk[2][200001], sum[2];
	inline void upd(int t, int x, int v)
	{
		for (; x < C2sz; x += x & (-x)) {fwk[t][x] += v;}
		sum[t] += v;
	}
	inline ll qry(int t, int x)
	{
		ll ret = 0; 
		for (; x; x -= x & (-x)) {ret += fwk[t][x];}
		return ret;
	}
};

int k, n, lfm, rgm; ll opt;
int C[200001], Csz = 0;
pii seg[2][100001]; int segSz[2]; 
ll res = 0;
BIT L[2], R[2];

inline void prep() 
{
	sort(C2, C2 + C2sz);
	C2sz = unique(C2, C2 + C2sz) - C2;
}

inline int getCoord(int x)
{
	return prev(upper_bound(C2, C2 + C2sz, x)) - C2;
}

inline ll eval(int k, int gx, int x)
{
	if (x < 0 || x > INF) return INF2;
	if (gx == -1) {gx = getCoord(x);}
	return L[k].qry(0, gx) * x - L[k].qry(1, gx) + (R[k].sum[1] - R[k].qry(1, gx)) - x * (R[k].sum[0] - R[k].qry(0, gx));
}

inline ll solve(int t, int lf, int rg)
{
	int M;
	while (rg - lf > 3)
	{
		int M = lf + ((rg - lf) >> 1);
		int gx = getCoord(M), gx2 = gx + (gx + 1 < C2sz && C2[gx + 1] == M + 1);
		if (eval(t, gx, M) < eval(t, gx2, M + 1)) {rg = M + 1;}
		else {lf = M;}
	}
	int ans = lf;
	for (int i = lf + 1; i <= rg; i++)
	{
		if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
	}
	return eval(t, -1, ans);
}

inline ll solve2(int t, int lf, int rg)
{
	while (rg - lf > 3)
	{
		int M = lf + ((rg - lf) >> 1);
		int gx = getCoord(M), gx2 = gx + (gx + 1 < C2sz && C2[gx + 1] == M + 1);
		if (eval(t, gx, M) < eval(t, gx2, M + 1)) {rg = M + 1;}
		else {lf = M;}
	}
	int ans = lf;
	for (int i = lf + 1; i <= rg; i++)
	{
		if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
	}
	return ans;
}

inline ll eval2(int x, int l, int r)
{
	if (l < 0 || r > INF || l > r) return INF2; 
	if (r < lfm) {return eval(0, -1, x) + eval(1, -1, r);}
	else if (l > rgm) {return eval(0, -1, x) + eval(1, -1, l);}
	else {return eval(0, -1, x) + opt;}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("bridges.in", "r", stdin);
	cin >> k >> n;
	C2[C2sz++] = -1;
	for (int i = 0; i < n; i++)
	{
		char c1, c2; int p1, p2; cin >> c1 >> p1 >> c2 >> p2;
		if (p1 > p2) swap(p1, p2);
		res += p2 - p1;
		if (c1 != c2) 
		{
			res++;
			seg[0][segSz[0]++] = {p1, p2};
			seg[1][segSz[1]++] = {p1 + p2, segSz[0] - 1};
			C[Csz++] = p1 + p2;
			C2[C2sz++] = p1;
			C2[C2sz++] = p2;
		}
	}
	prep();
	//cout << res << "\n";
	if (k == 1)
	{
		for (int i = 0; i < segSz[0]; i++)
		{
			int gx = getCoord(seg[0][i].snd);
			L[0].upd(0, gx, 1);
			L[0].upd(1, gx, seg[0][i].snd);
			gx = getCoord(seg[0][i].fst);
			R[0].upd(0, gx, 1);
			R[0].upd(1, gx, seg[0][i].fst);
		}
		cout << res + 2 * solve(0, 0, INF) << "\n";
	}
	else
	{
		sort(seg[1], seg[1] + segSz[1]);
		C[Csz++] = 0; C[Csz++] = 2 * INF; C[Csz++] = 2 * INF + 1;
		sort(C, C + Csz); 
		Csz = unique(C, C + Csz) - C;
		int j = 0;
		for (int i = 0; i < segSz[0]; i++)
		{
			int gx = getCoord(seg[0][i].snd);
			L[1].upd(0, gx, 1);
			L[1].upd(1, gx, seg[0][i].snd);
			gx = getCoord(seg[0][i].fst);
			R[1].upd(0, gx, 1);
			R[1].upd(1, gx, seg[0][i].fst);
		}
		ll ans = INF2;
		for (int i = 0; i < Csz - 1; i++)
		{
			for (; j < segSz[1] && seg[1][j].fst <= C[i]; j++)
			{
				int idx = seg[1][j].snd, gx = getCoord(seg[0][idx].snd);
				L[1].upd(0, gx, -1);
				L[1].upd(1, gx, -seg[0][idx].snd);
				L[0].upd(0, gx, 1);
				L[0].upd(1, gx, seg[0][idx].snd);

				gx = getCoord(seg[0][idx].fst);
				R[1].upd(0, gx, -1);
				R[1].upd(1, gx, -seg[0][idx].fst);
				R[0].upd(0, gx, 1);
				R[0].upd(1, gx, seg[0][idx].fst);
			}
			
			int idx = solve2(1, 0, INF); opt = eval(1, -1, idx);
			int l = 0, r = idx;
			while (l < r)
			{
				int M = l + ((r - l) >> 1);
				if (eval(1, -1, M) > opt) {l = M + 1;}
				else {r = M;}
			}
			lfm = l;

			l = idx, r = INF + 1;
			while (l < r)
			{
				int M = l + ((r - l) >> 1);
				if (eval(1, -1, M) > opt) {r = M;}
				else {l = M + 1;}
			}
			rgm = r - 1;

			l = max(0, C[i] - INF), r = C[i] / 2;
			while (r - l > 3)
			{
				int M = l + ((r - l) >> 1);
				if (eval2(M, C[i] - M, min(INF, C[i + 1] - 1 - M)) < eval2(M + 1, C[i] - M - 1, min(INF, C[i + 1] - 2 - M))) {r = M + 1;}
				else {l = M;}
			}
			assert(l <= r);
			int anss = l;
			for (int j = l + 1; j <= r; j++)
			{
				if (eval2(j, C[i] - j, min(INF, C[i + 1] - 1 - j)) < eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss))) {anss = j;}
			}
			ans = min(ans, eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss)));
		}
		cout << 2 * ans + res << "\n";
	}
	return 0;
}

Compilation message

bridge.cpp: In function 'long long int solve(int, int, int)':
bridge.cpp:60:6: warning: unused variable 'M' [-Wunused-variable]
   60 |  int M;
      |      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 26 ms 3968 KB Output is correct
13 Correct 100 ms 11692 KB Output is correct
14 Correct 59 ms 4344 KB Output is correct
15 Correct 63 ms 7088 KB Output is correct
16 Correct 40 ms 4728 KB Output is correct
17 Correct 66 ms 11736 KB Output is correct
18 Correct 58 ms 8184 KB Output is correct
19 Correct 106 ms 11452 KB Output is correct
20 Correct 34 ms 4984 KB Output is correct
21 Correct 67 ms 11400 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 14 ms 640 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 2 ms 420 KB Output is correct
20 Correct 17 ms 640 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 14 ms 512 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 10 ms 640 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 14 ms 640 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 15 ms 640 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 15 ms 640 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 10 ms 640 KB Output is correct
25 Correct 42 ms 3956 KB Output is correct
26 Correct 69 ms 4096 KB Output is correct
27 Execution timed out 2037 ms 16408 KB Time limit exceeded
28 Halted 0 ms 0 KB -