oj.uz

Submission #238812

# Submission time Handle Problem Language Result Execution time Memory
238812 2020-06-13T00:24:22 Z Jatana Meetings (IOI18_meetings) C++17
100 / 100
 3474 ms 325636 KB 
#include "meetings.h"
#include <algorithm>
#include <cassert>
#include <tuple>
#define le(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define f(i, n) for (int i = 0; i < (n); i++)
#define x first
#define y second

using namespace std;

typedef long long ll;

struct F {
	ll c = 0, a = 0, b = 0;
};
const ll INF = 1e18;
const F eye{0, 0, (ll)INF};

bool operator==(const F &a, const F &b) {
	return a.c == b.c && a.a == b.a && a.b == b.b;
}

typedef pair<ll, ll> line;

ll eval(line l, ll x) {
	return l.x * x + l.y;
}

ll eval(F func, ll x, ll y) {
	return min(x + func.c, 1LL * func.a * y + func.b);
}

struct TS {
	vector<F> func;
	int n;
	TS() {}
	TS(int _n) {
		n = _n;
		func.resize(2 * n, eye);
	}
	ll get(int i, int tl, int tr, int j) {
		if (tl + 1 == tr) return eval(func[i], 0, j);
		int m = (tl + tr) / 2;
		if (j < m) {
			return eval(func[i], get(i + 1, tl, m, j), j);
		} else return eval(func[i], get(i + (m - tl) * 2, m, tr, j), j);
	}
	ll get(int j) {
		return get(0, 0, n, j);
	}
	void act(int i, int tl, int tr, F h) {
		if (func[i] == eye) {
			func[i] = h;
			return;
		}
		line l1 = mp(func[i].a, func[i].b + h.c);
		line l2 = mp(h.a, h.b);
		func[i].c += h.c;
		l1.y -= func[i].c; l2.y -= func[i].c;
		int m = (tl + tr) / 2;
		if (eval(l1, m) > eval(l2, m))
			swap(l1, l2);
		func[i].a = l1.x; func[i].b = l1.y;
		func[i].b += func[i].c;
		if (tl + 1 != tr) {
			if (eval(l2, tl) < eval(l1, tl)) {
				act(i + 1, tl, m, {0, l2.x, l2.y});
			} else
				act(i + (m - tl) * 2, m, tr, {0, l2.x, l2.y});
		}
	}
	void app(int i, int tl, int tr, int ql, int qr, F h) {
		if (tr <= ql || qr <= tl) return;
		if (ql <= tl && tr <= qr) {
			act(i, tl, tr, h);
		} else {
			int m = (tl + tr) / 2;
			// assert(func[i] == eye);
			app(i + 1, tl, m, ql, qr, h);
			app(i + (m - tl) * 2, m, tr, ql, qr, h);
		}
	}
};

vector<int> H;
vector<int> mx[21];
#include <numeric>
int query(int l, int r) {
	int p = 31 - __builtin_clz(r - l);
	int a = mx[p][l];
	int b = mx[p][r - (1 << p)];
	if (H[a] >= H[b]) return a;
	return b;
}
void init() {
	mx[0] = vector<int>(le(H), 0);
	iota(mx[0].begin(), mx[0].end(), 0);
	for (int i = 1; i < 21; i++) {
		mx[i] = mx[i - 1];
		for (int j = 0; j < le(H); j++) {
			int sub = j + (1 << (i - 1));
			if (sub < le(H)) {
				if (H[mx[i - 1][sub]] > H[mx[i][j]]) {
					mx[i][j] = mx[i - 1][sub];
				}
			}
		}
	}
}

vector<ll> dp[2];
TS sp[2];
vector<int> L;
vector<int> R;
vector<ll> rez;
vector<vector<int>> qs;

void process(int l, int r, int m) {
	for (int id : qs[m]) {
		// either left or right
		rez[id] = min(
			sp[0].get(0, 0, sp[0].n, R[id]) + 1LL * H[m] * (m - L[id] + 1),
			sp[1].get(0, 0, sp[1].n, L[id]) + 1LL * H[m] * (R[id] - m + 1)
		);
	}
	dp[0][m] = (m - 1 >= l ? sp[0].get(m - 1) : 0) + H[m];
	sp[0].app(0, 0, sp[0].n, m, m + 1, {dp[0][m], 0, (ll)INF});
	sp[0].app(0, 0, sp[0].n, m + 1, r, {
		1LL * (m - l + 1) * H[m],
		H[m],
		dp[0][m] - 1LL * m * H[m]
	});
	// for (int i = m + 1; i < r; i++) {
	// 	dp[0][i] = min(
	// 		dp[0][i] + 1LL * (m - l + 1) * H[m],
	// 		dp[0][m] + 1LL * (i - m) * H[m]
	// 	);
	// }
	dp[1][m] = (m + 1 < r ? sp[1].get(m + 1) : 0) + H[m];
	sp[1].app(0, 0, sp[1].n, m, m + 1, {dp[1][m], 0, (ll)INF});
	sp[1].app(0, 0, sp[1].n, l, m, {
		1LL * (r - m) * H[m],
		-1LL * H[m],
		dp[1][m] + 1LL * m * H[m]
	});
}
vector<tuple<int, int, int>> work;
void go(int l, int r) {
	if (l >= r) return;
	if (l + 1 == r) {
		f(t, 2) {
			dp[t][l] = H[l];
			sp[t].app(0, 0, sp[t].n, l, l + 1, {H[l], 0, (ll)INF});
		}
		for (int id : qs[l]) {
			rez[id] = H[l];
		}
		return;
	}
	int m = query(l, r);
	// for (int i = l; i < r; i++)
		// if (H[i] > H[m]) 
			// m = i;
	go(l, m);
	go(m + 1, r);
	work.emplace_back(l, r, m);
	// for (int i = m - 1; i >= l; i--) {
	// 	dp[1][i] = min(
	// 		dp[1][i] + 1LL * (r - m) * H[m],
	// 		dp[1][m] + 1LL * (m - i) * H[m]
	// 	);
	// }
}

vector<ll> minimum_costs(vector<int> _H, vector<int> _L,
    vector<int> _R) {
	L = _L; 
	R = _R;
	H = _H;//H = vector<int>(750'000, 3);
	init();
	dp[0].resize(le(H));
	dp[1].resize(le(H));
	sp[0] = TS(le(H));
	sp[1] = TS(le(H));
	qs.resize(le(H));
  int Q = L.size();
	for (int i = 0; i < Q; i++) {
		// int pos = max_element(H.begin() + L[i], H.begin() + R[i] + 1) - H.begin();
		int pos = query(L[i], R[i] + 1);
		qs[pos].pb(i);
	}
	rez.resize(Q, (ll)1e18);
	// return {};
	go(0, le(H));
	for (auto ttt : work) {
		process(get<0>(ttt), get<1>(ttt), get<2>(ttt));
	}
  return rez;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 7 ms 1024 KB Output is correct
4 Correct 7 ms 1152 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 8 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 7 ms 1024 KB Output is correct
4 Correct 7 ms 1152 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 8 ms 1152 KB Output is correct
10 Correct 12 ms 1792 KB Output is correct
11 Correct 12 ms 1792 KB Output is correct
12 Correct 13 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 13 ms 2176 KB Output is correct
15 Correct 12 ms 1792 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 48 ms 5112 KB Output is correct
3 Correct 235 ms 34668 KB Output is correct
4 Correct 212 ms 29176 KB Output is correct
5 Correct 228 ms 36716 KB Output is correct
6 Correct 243 ms 37228 KB Output is correct
7 Correct 289 ms 37996 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 48 ms 5112 KB Output is correct
3 Correct 235 ms 34668 KB Output is correct
4 Correct 212 ms 29176 KB Output is correct
5 Correct 228 ms 36716 KB Output is correct
6 Correct 243 ms 37228 KB Output is correct
7 Correct 289 ms 37996 KB Output is correct
8 Correct 195 ms 29168 KB Output is correct
9 Correct 171 ms 29088 KB Output is correct
10 Correct 182 ms 29180 KB Output is correct
11 Correct 195 ms 28668 KB Output is correct
12 Correct 177 ms 28524 KB Output is correct
13 Correct 180 ms 28788 KB Output is correct
14 Correct 220 ms 34420 KB Output is correct
15 Correct 177 ms 28380 KB Output is correct
16 Correct 272 ms 35308 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 7 ms 1024 KB Output is correct
4 Correct 7 ms 1152 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 8 ms 1152 KB Output is correct
10 Correct 12 ms 1792 KB Output is correct
11 Correct 12 ms 1792 KB Output is correct
12 Correct 13 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 13 ms 2176 KB Output is correct
15 Correct 12 ms 1792 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 48 ms 5112 KB Output is correct
18 Correct 235 ms 34668 KB Output is correct
19 Correct 212 ms 29176 KB Output is correct
20 Correct 228 ms 36716 KB Output is correct
21 Correct 243 ms 37228 KB Output is correct
22 Correct 289 ms 37996 KB Output is correct
23 Correct 195 ms 29168 KB Output is correct
24 Correct 171 ms 29088 KB Output is correct
25 Correct 182 ms 29180 KB Output is correct
26 Correct 195 ms 28668 KB Output is correct
27 Correct 177 ms 28524 KB Output is correct
28 Correct 180 ms 28788 KB Output is correct
29 Correct 220 ms 34420 KB Output is correct
30 Correct 177 ms 28380 KB Output is correct
31 Correct 272 ms 35308 KB Output is correct
32 Correct 1720 ms 213920 KB Output is correct
33 Correct 1410 ms 215244 KB Output is correct
34 Correct 1598 ms 212348 KB Output is correct
35 Correct 1839 ms 213680 KB Output is correct
36 Correct 1373 ms 215564 KB Output is correct
37 Correct 1611 ms 212536 KB Output is correct
38 Correct 2285 ms 258168 KB Output is correct
39 Correct 2306 ms 258272 KB Output is correct
40 Correct 2112 ms 221192 KB Output is correct
41 Correct 3368 ms 322480 KB Output is correct
42 Correct 3474 ms 325636 KB Output is correct
43 Correct 3421 ms 325604 KB Output is correct
44 Correct 2750 ms 276424 KB Output is correct