Submission #108312

#	Time	Username	Problem	Language	Result	Execution time	Memory
108312		Noam527	Meetings (IOI18_meetings)	C++17	100 / 100	5373 ms	312008 KiB

meetings

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct func {
	int a;
	ll b, c;
	func() {
		a = 1, b = c = 0;
	}
	func(int aa, ll bb, ll cc) : a(aa), b(bb), c(cc) {}
	// this * x
	func operator * (const func &x) const {
		return func(a * x.a, a * x.b + b, a * x.c + c);
	}
	// x * this
	void operator *= (const func &x) {
		a = x.a * a;
		b = x.a * b + x.b;
		c = x.a * c + x.c;
	}
	ll operator () (ll x, int i) const {
		return a * x + b * i + c;
	}
};

struct segtree {
	int n;
	vector<ll> t;
	vector<int> ind;
	vector<func> tag;
	segtree() {}
	segtree(int sz) {
		init(sz);
	}
	void init(int sz) {
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n, 0);
		tag.resize(2 * n, func());
		ind.resize(2 * n);
		for (int i = 0; i < n; i++)
			ind[i + n - 1] = i;
		for (int i = n - 2; i >= 0; i--)
			ind[i] = ind[2 * i + 1];
	}
	void clear() {
		for (auto &i : t) i = 0;
		for (auto &i : tag) i = func();
	}
	void push(int x) {
		t[x] = tag[x](t[x], ind[x]);
		if (x < n - 1) {
			tag[2 * x + 1] *= tag[x];
			tag[2 * x + 2] *= tag[x];
		}
		tag[x] = func();
	}
	// assumes x has no tag
	void fix(int x) {
		push(2 * x + 1);
		t[x] = t[2 * x + 1];
	}
	// a[i] = x
	void set(ll x, int i) {
		func f(0, 0, x);
		upd(i, i, f, 0, 0, n - 1);
	}
	inline func progressf(int l, int r, ll st, ll d) {
		return func(1, d, st - d * l);
	}
	// for each i in [l, r], add st + d * (i - l)
	void progress(int l, int r, ll st, ll d) {
		func f(1, d, st - d * l);
		upd(l, r, f, 0, 0, n - 1);
	}
	// for each i in monotonic [l, r], set a[i] = min(a[i], x)
	void minimize(int l, int r, ll x) {
		int m = last(l, r, x);
		if (m != -1) {
			func f(0, 0, x);
			upd(l, m, f, 0, 0, n - 1);
		}
	}
	void upd(int l, int r, const func &f, int node, int nl, int nr) {
		if (r < nl || nr < l) return;
		if (l <= nl && nr <= r) {
			tag[node] *= f;
			return;
		}
		push(node);
		int mid = (nl + nr) / 2;
		upd(l, r, f, 2 * node + 1, nl, mid);
		upd(l, r, f, 2 * node + 2, mid + 1, nr);
		fix(node);
	}
	// smallest i in [l, r] s.t a[i] >= x
	int last(int l, int r, ll x) {
		return last(l, r, x, 0, 0, n - 1);
	}
	int last(int l, int r, ll x, int node, int nl, int nr) {
		if (r < nl || nr < l) return -1;
		push(node);
		if (l <= nl && nr <= r && t[node] < x) return -1;
		if (nl == nr) return nl;
		int mid = (nl + nr) / 2, tmp;
		tmp = last(l, r, x, 2 * node + 2, mid + 1, nr);
		if (tmp != -1) return tmp;
		return last(l, r, x, 2 * node + 1, nl, mid);
	}
	ll operator [] (int i) const {
		int org = i;
		i += n - 1;
		ll rtn = t[i];
		rtn = tag[i](rtn, org);
		i = (i - 1) / 2;
		while (i) {
			rtn = tag[i](rtn, org);
			i = (i - 1) / 2;
		}
		rtn = tag[0](rtn, org);
		return rtn;
	}
};

struct mtree {
	int n;
	const ll b = 1 << 30;
	vector<ll> t;
	mtree() {}
	mtree(const vector<int> &a) {
		init(a);
	}
	void init(const vector<int> &a) {
		n = max(2, (int)a.size());
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
		for (int i = 0; i < a.size(); i++)
			t[i + n - 1] = b * a[i] + i;
		for (int i = n - 2; i >= 0; i--)
			t[i] = max(t[2 * i + 1], t[2 * i + 2]);
	}
	int query(int l, int r) const {
		ll mx = -1;
		for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
			if (!(l & 1)) mx = max(mx, t[l++]);
			if (r & 1) mx = max(mx, t[r--]);
		}
		if (l == r) mx = max(mx, t[l]);
		return mx % b;
	}
	ll vquery(int l, int r) const {
		ll mx = -1;
		for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
			if (!(l & 1)) mx = max(mx, t[l++]);
			if (r & 1) mx = max(mx, t[r--]);
		}
		if (l == r) mx = max(mx, t[l]);
		return mx / b;
	}
};

struct query {
	int l, r, i;
	query() {}
	query(int ll, int rr, int ii) : l(ll), r(rr), i(ii) {}
};

const int mxn = 750005;

int n;
vector<int> a;
int S[mxn], E[mxn], L[mxn], R[mxn], root;
vector<query> Q[mxn];
vector<ll> ans;

mtree M;
segtree T;

int preprocess(int l, int r) {
	if (l > r) return -1;
	int v = M.query(l, r);
	if (OO) {
		cout << "preprocessing in [" << l << ", " << r << "], v = " << v << '\n';
	}
	S[v] = l;
	E[v] = r;
	L[v] = preprocess(l, v - 1);
	R[v] = preprocess(v + 1, r);
	return v;
}

void preprocess(const vector<int> &l, const vector<int> &r) {
	M.init(a);
	T.init(n);
	root = preprocess(0, n - 1);
	for (int i = 0; i < ans.size(); i++) {
		ans[i] = ll(r[i] - l[i] + 1) * M.vquery(l[i], r[i]);
		int v = M.query(l[i], r[i]);
		if (OO) {
			cout << "attaching query " << l[i] << " " << r[i] << " to " << v << '\n';
		}
		Q[v].push_back(query(l[i], r[i], i));
	}
}

void solve(int v, int prev) {
	if (v < 0 || n <= v) return;
	solve(L[v], v);
	solve(R[v], v);
	if (OO) cout << "solving " << v << " " << prev << '\n';
	if (OO) {
		cout << "before:\n";
		for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
	}
	
	if (S[v] == v) T.set(a[v], v);
	else T.set(T[v - 1] + a[v], v);
	if (v < E[v]) {
		ll c = (v > 0 ? T[v - 1] : 0) + (ll)a[v] * (1 - (v - S[v]));
		/*
		T.progress(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0);
		T.progress(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]);
		*/
		func tmp = T.progressf(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0);
		tmp *= T.progressf(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]);
		T.upd(v + 1, E[v], tmp, 0, 0, T.n - 1);
		T.minimize(v + 1, E[v], c);
		T.progress(v + 1, E[v], ll(v - S[v] + 1) * a[v], a[v]);
	}
	if (OO) {
		cout << "after:\n";
		for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
	}

	if (prev != -1 && prev < v) {
		for (const auto &i : Q[prev]) {
			if (prev < i.r) {
				if (OO) cout << "updating query " << i.l << " " << i.r << '\n';
				ans[i.i] = min(ans[i.i], ll(prev - i.l + 1) * a[prev] + T[i.r]);
			}
		}
	}
}

ll cost(int l, int r, int i) {
	ll rtn = a[i], mx;
	mx = a[i];
	for (int x = i + 1; x <= r; x++) {
		mx = max(mx, (ll)a[x]);
		rtn += mx;
	}
	mx = a[i];
	for (int x = i - 1; x >= l; x--) {
		mx = max(mx, (ll)a[x]);
		rtn += mx;
	}
	return rtn;
}

ll bruteforce(int l, int r) {
	ll ans = inf;
	for (int i = l; i <= r; i++)
		ans = min(ans, cost(l, r, i));
	return ans;
}

vector<ll> minimum_costs(vector<int> H, vector<int> l,
	vector<int> r) {
	n = H.size();
	a = H;
	ans.resize(l.size());

	preprocess(l, r);
	if (OO) {
		cout << "preprocessed\n";
		cout << "L: ";
		for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
		cout << "R: ";
		for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
		cout << "S: ";
		for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
		cout << "E: ";
		for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
	}
	solve(root, -1);
	// reverse
	reverse(a.begin(), a.end());
	auto flip = [](int &x, int y) {
		x = y - 1 - x;
	};
	for (int i = 0; i < n; i++) {
		flip(S[i], n);
		flip(E[i], n);
		swap(S[i], E[i]);
		flip(L[i], n);
		flip(R[i], n);
		swap(L[i], R[i]);
	}
	for (int i = 0; i < n; i++) {
		for (auto &j : Q[i]) {
			flip(j.l, n);
			flip(j.r, n);
			swap(j.l, j.r);
		}
	}
	reverse(Q, Q + n);
	reverse(S, S + n);
	reverse(E, E + n);
	reverse(L, L + n);
	reverse(R, R + n);
	M.init(a);
	T.clear();
	flip(root, n);
	if (OO) {
		cout << "reversed\n";
		cout << "L: ";
		for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
		cout << "R: ";
		for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
		cout << "S: ";
		for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
		cout << "E: ";
		for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
		cout << '\n';
		cout << "current answers: ";
		for (const auto &i : ans) cout << i << " "; cout << '\n';
	}
	solve(root, -1);
	return ans;
}

Compilation message (stderr)

meetings.cpp: In member function 'void mtree::init(const std::vector<int>&)':
meetings.cpp:145:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++)
                   ~~^~~~~~~~~~
meetings.cpp: In function 'void preprocess(const std::vector<int>&, const std::vector<int>&)':
meetings.cpp:204:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:221:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
   ^~~
meetings.cpp:221:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:240:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
   ^~~
meetings.cpp:240:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:285:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
   ^~~
meetings.cpp:285:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:287:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
   ^~~
meetings.cpp:287:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:289:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
   ^~~
meetings.cpp:289:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:291:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
   ^~~
meetings.cpp:291:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:325:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
   ^~~
meetings.cpp:325:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:327:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
   ^~~
meetings.cpp:327:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:329:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
   ^~~
meetings.cpp:329:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:331:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
   ^~~
meetings.cpp:331:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:334:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ans) cout << i << " "; cout << '\n';
   ^~~
meetings.cpp:334:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ans) cout << i << " "; cout << '\n';
                                               ^~~~

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