Submission #298610

#	Time	Username	Problem	Language	Result	Execution time	Memory
298610		cookiedoth	Meetings (IOI18_meetings)	C++14	100 / 100	3955 ms	558112 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;
	}
};

struct fenwick {
	fenwick() {}

	vector<ll> t;
	int n;

	fenwick(int _n) {
		n = _n;
		t.resize(n);
	}

	void add(int pos, ll val) {
		while (pos < n) {
			t[pos] += val;
			pos = pos | (pos + 1);
		}
	}

	ll get(int pos) {
		ll res = 0;
		while (pos >= 0) {
			res += t[pos];
			pos = (pos & (pos + 1)) - 1;
		}
		return res;
	}
};

struct superfenwick {
	superfenwick() {}

	fenwick F;

	superfenwick(int _n) {
		F = fenwick(_n + 1);
	}

	void add(int l, int r, ll val) {
		F.add(l, val);
		F.add(r + 1, -val);
	}

	ll get(int pos) {
		return F.get(pos);
	}
};

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;
superfenwick F;

struct segment {
	int start;
	ll a, b;

	ll get(int pos) {
		return a + b * pos;
	}

	segment(int _start, ll _a, ll _b): start(_start), a(_a), b(_b) {}
};

bool operator < (const segment &a, const segment &b) {
	return a.start < b.start;
}

void print(deque<segment> *d, int l, int r) {
	cerr << "print " << l << " " << r << endl;
	for (int i = 0; i < length(*d); ++i) {
		int R = (i == length(*d) - 1 ? r : (*d)[i + 1].start - 1);
		// cerr << "segment " << (*d)[i].start << ' ' << R << '\n';
		for (int j = (*d)[i].start; j <= R; ++j) {
			cerr << (*d)[i].a + (*d)[i].b * j + F.get(j) << ' ';
		}
	}
	cerr << '\n';
}
 
deque<segment>* go(int l, int r) {
	if (l > r) {
		return new deque<segment> ();
	}
	if (l == r) {
		deque<segment>* cur = new deque<segment> ();
		cur->emplace_back(l, h[l], 0);
		for (auto query : Q_by_argmax[l]) {
			chkmin(ans[query.id], h[l]);
		}
		return cur;
	}
	int pos = T.get(l, r).second;
	ll H = h[pos];
	auto d1 = go(l, pos - 1);
	auto d2 = go(pos + 1, r);
	// cerr << "================merge " << l << " " << r << endl;
	// cerr << "H = " << H << endl;
	// if (!d1->empty()) {
	// 	print(d1, l, pos - 1);
	// }
	// if (!d2->empty()) {
	// 	print(d2, pos + 1, r);
	// }
	ll pos_val = (d1->empty() ? 0 : d1->back().get(pos - 1) + F.get(pos - 1)) + h[pos];
	// cerr << "pos_val = " << pos_val << endl;
	for (auto query : Q_by_argmax[pos]) {
		if (query.r == pos) {
			chkmin(ans[query.id], H * (pos - query.l + 1));
		} else {
			segment to_seach = {query.r, 0, 0};
			int d2_pos = upper_bound(d2->begin(), d2->end(), to_seach) - 1 - d2->begin();
			chkmin(ans[query.id], (*d2)[d2_pos].get(query.r) + F.get(query.r) + H * (pos - query.l + 1));
			// cerr << H * (pos - query.l + 1) << endl;
			// cerr << "kek " << ans[query.id] << endl;
		}
	}
	d1->emplace_back(pos, pos_val, 0);
	if (pos + 1 <= r) {
		ll f1 = pos_val;
		ll f2 = H * (pos - l + 1);
		while (!d2->empty()) {
			int back_pos = (d2->size() > 1 ? (*d2)[1].start - 1 : r);
			ll mod = F.get(back_pos);
			// cerr << "check " << back_pos << endl;
			// cerr << (*d2)[0].get(back_pos) + mod + f2 << endl;
			// cerr << f1 + H * (back_pos - pos) << endl;
			// cerr << "f2 = " << f2 << endl;
			if ((*d2)[0].get(back_pos) + mod + f2 <= f1 + H * (back_pos - pos)) {
				// cerr << "opa back_pos = " << back_pos << endl;
				// cerr << "back_res = " << f1 + H * (back_pos - pos) << endl;
				// cerr << "back_res_opt = " << (*d2)[0].get(back_pos) + mod + f2 << endl;
				// cerr << "f1 = " << f1 << endl;
				// cerr << "pos = " << pos << endl;
				// cerr << "H = " << H << endl;
				// cerr << "a = " << (*d2)[0].a << endl;
				// cerr << "mod = " << mod << endl;
				// cerr << "b = " << (*d2)[0].b << endl;
				// cerr << "LR = " << (*d2)[0].start << " " << back_pos << endl;
				// cerr << "f2 = " << f2 << endl;
				ll div1 = (*d2)[0].a + mod + f2 - f1 + H * pos;
				ll div2 = (H - (*d2)[0].b);
				int threshold;
				if (div2 == 0) {
					threshold = (*d2)[0].start;
				} else {
					threshold = (div1 + div2 - 1) / div2;
				}
				// cerr << "threshold = " << threshold << endl;
				chkmax(threshold, (*d2)[0].start);
				assert(threshold <= back_pos);
				F.add((*d2)[0].start, threshold - 1, -mod);
				(*d2)[0].start = threshold;
				F.add(threshold, r, f2);
				if (threshold > pos + 1) {
					d2->push_front({pos + 1, f1 - H * pos, H});
				}
				// cerr << "opa " << (*d2)[0].start << endl;
				// cerr << "kek " << (*d2)[1].start << endl;
				// cerr << d2->size() << endl;
				break;
			} else {
				F.add((*d2)[0].start, back_pos, -mod);
				d2->pop_front();
			}
		}
		if (d2->empty()) {
			d2->push_front({pos + 1, f1 - H * pos, H});
		}
	}
	if (d1->size() > d2->size()) {
		for (auto x : (*d2)) {
			d1->push_back(x);
		}
		delete d2;
		// print(d1, l, r);
		return d1;
	} else {
		for (int i = (int)d1->size() - 1; i >= 0; --i) {
			d2->push_front((*d1)[i]);
		}
		delete d1;
		// print(d2, l, r);
		return d2;
	}
}
 
void solve(int idx_sign) {
	// cerr << "solve " << idx_sign << endl;
	F = superfenwick(n);
	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]);
	}
	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: 40 / 40