Submission #297765

#	Time	Username	Problem	Language	Result	Execution time	Memory
297765		cookiedoth	Meetings (IOI18_meetings)	C++14	100 / 100	5322 ms	385680 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()
#pragma GCC optimize("Ofast")

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;
	}
};

int it = 0;

struct progST {
	progST() {}

	int n;
	vector<ll> mod_a, mod_b, t;
	vector<int> set_push, not_leaf;

	progST(int _n) {
		n = _n;
		// cerr << "build " << n << endl;
		mod_a.resize(4 * n);
		mod_b.resize(4 * n);
		set_push.resize(4 * n);
		t.resize(4 * n);
	}

	void update_t(int v, int tl, int tr) {
		if (set_push[v]) {
			t[v] = mod_a[v] + mod_b[v] * (tr - tl);
		} else {
			t[v] += mod_a[v];
		}
	}

	ll get(int v, int tl, int tr) {
		return (set_push[v] ? mod_a[v] + mod_b[v] * (tr - tl) : t[v] + mod_a[v]);
	}

	void push(int v, int tl, int tr) {
		update_t(v, tl, tr);
		if (tl != tr) {
			int tm = (tl + tr) >> 1;
			ll rval = mod_a[v] + mod_b[v] * (tm + 1 - tl);
			if (set_push[v]) {
				mod_a[v * 2] = mod_a[v];
				mod_a[v * 2 + 1] = rval;
				mod_b[v * 2 + 1] = mod_b[v * 2] = mod_b[v];
				set_push[v * 2] = set_push[v * 2 + 1] = 1;
			} else {
				mod_a[v * 2] += mod_a[v];
				mod_a[v * 2 + 1] += rval;
			}
		}
		set_push[v] = 0;
		mod_a[v] = mod_b[v] = 0;
	}

	void add(int l, int r, ll a, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return;
		}
		push(v, tl, tr);
		if (l <= tl && tr <= r) {
			mod_a[v] += a;
			// cerr << "mod_ab " << v << " " << mod_a[v] << " " << mod_b[v] << endl;
			return;
		}
		int tm = (tl + tr) >> 1;
		add(l, r, a, v * 2, tl, tm);
		add(l, r, a, v * 2 + 1, tm + 1, tr);
		// cerr << "opa push " << v * 2 + 1 << endl;
		push(v * 2 + 1, tm + 1, tr);
		t[v] = t[v * 2 + 1];
	}

	void print() {
		int res = get(n - 1);
		for (int i = 0; i < n; ++i) {
			cerr << get(i) << ' ';
		}
		cerr << '\n';
		output(all(mod_a));
		output(all(mod_b));
		output(all(t));
	}

	void add(int l, int r, ll a) {
		// cerr << "add " << l << " " << r << " " << a << " " << b << endl;
		add(l, r, a, 1, 0, n - 1);
		// print();
	}

	void set_val(int l, int r, ll a, ll b, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return;
		}
		push(v, tl, tr);
		if (l <= tl && tr <= r) {
			mod_a[v] = a + b * (tl - l);
			mod_b[v] = b;
			set_push[v] = 1;
			return;
		}
		int tm = (tl + tr) >> 1;
		set_val(l, r, a, b, v * 2, tl, tm);
		set_val(l, r, a, b, v * 2 + 1, tm + 1, tr);
		// push(v * 2 + 1, tm + 1, tr);
		t[v] = get(v * 2 + 1, tm + 1, tr);
	}

	void set_val(int l, int r, ll a, ll b) {
		// cerr << "set_val " << l << " " << r << " " << a << " " << b << endl;
		set_val(l, r, a, b, 1, 0, n - 1);
		// print();
	}

	ll get(int pos, int v, int tl, int tr) {
		// cerr << "push " << v << endl;
		// cerr << "data " << mod_a[v] << " " << mod_b[v] << " " << t[v] << endl;
		push(v, tl, tr);
		if (tl == tr) {
			return t[v];
		}
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			return get(pos, v * 2, tl, tm);
		} else {
			return get(pos, v * 2 + 1, tm + 1, tr);
		}
	}

	ll get(int pos) {
		// cerr << "get " << pos << endl;
		ll res = get(pos, 1, 0, n - 1);
		// cerr << "get " << pos << " = " << res << endl;
		return res;
	}

	int get_bound2(int l, int r, ll f1, ll step, ll f2, int v, int tl, int tr) {
		push(v, tl, tr);
		if (tl == tr) {
			return tl;
		}
		int tm = (tl + tr) >> 1;
		push(v * 2, tl, tm);
		if (t[v * 2] + f2 <= f1 + step * (tm - l + 1)) {
			return get_bound2(l, r, f1, step, f2, v * 2, tl, tm);
		} else {
			return get_bound2(l, r, f1, step, f2, v * 2 + 1, tm + 1, tr);
		}
	}

	int get_bound(int l, int r, ll f1, ll step, ll f2, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return -1;
		}
		push(v, tl, tr);
		if (l <= tl && tr <= r) {
			if (t[v] + f2 <= f1 + step * (tr - l + 1)) {
				return get_bound2(l, r, f1, step, f2, v, tl, tr);
			} else {
				return -1;
			}
		}
		int tm = (tl + tr) >> 1;
		int res1 = get_bound(l, r, f1, step, f2, v * 2, tl, tm);
		if (res1 != -1) {
			return res1;
		} else {
			return get_bound(l, r, f1, step, f2, v * 2 + 1, tm + 1, tr);
		}
	}

	int get_bound(int l, int r, ll f1, ll step, ll f2) {
		// cerr << "get_bound " << l << " " << r << " " << f1 << " " << step << " " << f2 << endl;
		int res = get_bound(l, r, f1, step, f2, 1, 0, n - 1);
		if (res == -1) {
			return r + 1;
		}
		return res;
	}
};

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]);
		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);
	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);
		// cerr << "z = " << z << endl;
		solver.set_val(pos + 1, z - 1, f1 + H, H);
		solver.add(z, r, f2);
	}
}

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);
}

Compilation message (stderr)

meetings.cpp: In member function 'void progST::print()':
meetings.cpp:214:7: warning: unused variable 'res' [-Wunused-variable]
  214 |   int res = get(n - 1);
      |       ^~~

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