Submission #297708

#	Time	Username	Problem	Language	Result	Execution time	Memory
297708		cookiedoth	Meetings (IOI18_meetings)	C++14	60 / 100	5554 ms	202828 KiB

meetings

/*

Code for problem C by cookiedoth
Generated 11 Sep 2020 at 10.19 PM


СТРОИМ СТЕНУ РАБОТЯГИ!
█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

z_z
>_<
¯\_(ツ)_/¯

*/

#include "meetings.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#include <utility>
#include <tuple>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct rmq {
	vector<pair<ll, int> > t;
	int n0, n, idx_sign;

	rmq() {}

	void build(ll *h, int v, int tl, int tr) {
		if (tl == tr) {
			if (tl < n0) {
				t[v] = {h[tl], tl * idx_sign};
			}
		} else {
			int tm = (tl + tr) >> 1;
			build(h, v * 2, tl, tm);
			build(h, v * 2 + 1, tm + 1, tr);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	rmq(ll *h, int _n, int _idx_sign) {
		n0 = _n;
		n = 1;
		while (n < _n) {
			n <<= 1;
		}
		t.resize(2 * n);
		idx_sign = _idx_sign;
		build(h, 1, 0, n - 1);
	}

	pair<ll, int> get(int l, int r) {
		pair<ll, int> res = {-1, -1};
		l += n;
		r += n;
		while (l <= r) {
			if (l & 1) {
				res = max(res, t[l++]);
			}
			if ((r & 1) == 0) {
				res = max(res, t[r--]);
			}
			l >>= 1;
			r >>= 1;
		}
		res.second *= idx_sign;
		return res;
	}
};

struct progST {
	progST() {}

	vector<ll> arr;
	int n;

	progST(int _n) {
		n = _n;
		arr.resize(n);
	}

	void add(int l, int r, ll a, ll b) {
		for (int i = l; i <= r; ++i) {
			arr[i] += a + b * (i - l);
		}
	}

	void set(int l, int r, ll a, ll b) {
		for (int i = l; i <= r; ++i) {
			arr[i] = a + b * (i - l);
		}
	}

	ll get(int pos) {
		return arr[pos];
	}

	int get_bound(int l, int r, ll f1, ll step, ll f2) {
		for (int i = l; i <= r; ++i) {
			if (arr[i] + f2 <= f1 + step * (i - l + 1)) {
				return i;
			}
		}
		return r + 1;
	}
};

struct query {
	int l, r, id;
};

const ll INF = 1e18 + 228;
const int mx = 8e5 + 228;
int n, q;
ll h[mx], ans[mx];
vector<vector<query> > Q_by_argmax;
vector<query> Q;
rmq T;
progST solver;

void go(int l, int r) {
	if (l > r) {
		return;
	}
	if (l == r) {
		solver.add(l, r, h[l], 0);
		for (auto query : Q_by_argmax[l]) {
			chkmin(ans[query.id], h[l]);
		}
		return;
	}
	int pos = T.get(l, r).second;
	ll H = h[pos];
	go(l, pos - 1);
	go(pos + 1, r);
	for (auto query : Q_by_argmax[pos]) {
		chkmin(ans[query.id], solver.get(query.r) + H * (pos - query.l + 1));
	}
	ll val = (l < pos ? solver.get(pos - 1) : 0LL) + H;
	solver.add(pos, pos, val, 0);
	if (pos + 1 <= r) {
		ll f1 = solver.get(pos);
		ll f2 = H * (pos - l + 1);
		int z = solver.get_bound(pos + 1, r, f1, H, f2);
		solver.set(pos + 1, z - 1, f1 + H, H);
		solver.add(z, r, f2, 0);
	}
}

void solve(int idx_sign) {
	// cerr << "solve " << idx_sign << endl;
	Q_by_argmax.assign(n, vector<query> ());
	T = rmq(h, n, idx_sign);
	for (int i = 0; i < q; ++i) {
		Q_by_argmax[T.get(Q[i].l, Q[i].r).second].push_back(Q[i]);
	}
	solver = progST(n);
	go(0, n - 1);
	// cerr << ans[0] << endl;
}

void flip() {
	reverse(h, h + n);
	for (int i = 0; i < q; ++i) {
		Q[i].l = n - 1 - Q[i].l;
		Q[i].r = n - 1 - Q[i].r;
		swap(Q[i].l, Q[i].r);
	}
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	for (int i = 0; i < q; ++i) {
		Q.push_back({L[i], R[i], i});
	}
	for (int i = 0; i < n; ++i) {
		h[i] = H[i];
	}
	fill(ans, ans + q, INF);
	solve(1);
	flip();
	solve(-1);
	return vector<ll> (ans, ans + q);
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40