Submission #238812

#	Time	Username	Problem	Language	Result	Execution time	Memory
238812		Jatana	Meetings (IOI18_meetings)	C++17	100 / 100	3474 ms	325636 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40