oj.uz

Submission #108312

# Submission time Handle Problem Language Result Execution time Memory
108312 2019-04-28T13:43:36 Z Noam527 Meetings (IOI18_meetings) C++17
100 / 100
 5373 ms 312008 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18012 KB Output is correct
2 Correct 26 ms 18396 KB Output is correct
3 Correct 27 ms 18388 KB Output is correct
4 Correct 26 ms 18396 KB Output is correct
5 Correct 28 ms 18372 KB Output is correct
6 Correct 28 ms 18700 KB Output is correct
7 Correct 27 ms 18412 KB Output is correct
8 Correct 28 ms 18772 KB Output is correct
9 Correct 29 ms 18552 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18012 KB Output is correct
2 Correct 26 ms 18396 KB Output is correct
3 Correct 27 ms 18388 KB Output is correct
4 Correct 26 ms 18396 KB Output is correct
5 Correct 28 ms 18372 KB Output is correct
6 Correct 28 ms 18700 KB Output is correct
7 Correct 27 ms 18412 KB Output is correct
8 Correct 28 ms 18772 KB Output is correct
9 Correct 29 ms 18552 KB Output is correct
10 Correct 37 ms 19112 KB Output is correct
11 Correct 37 ms 19148 KB Output is correct
12 Correct 37 ms 19100 KB Output is correct
13 Correct 37 ms 19104 KB Output is correct
14 Correct 39 ms 19560 KB Output is correct
15 Correct 37 ms 19184 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18012 KB Output is correct
2 Correct 91 ms 22184 KB Output is correct
3 Correct 560 ms 46552 KB Output is correct
4 Correct 521 ms 37028 KB Output is correct
5 Correct 510 ms 47648 KB Output is correct
6 Correct 559 ms 48672 KB Output is correct
7 Correct 625 ms 51264 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18012 KB Output is correct
2 Correct 91 ms 22184 KB Output is correct
3 Correct 560 ms 46552 KB Output is correct
4 Correct 521 ms 37028 KB Output is correct
5 Correct 510 ms 47648 KB Output is correct
6 Correct 559 ms 48672 KB Output is correct
7 Correct 625 ms 51264 KB Output is correct
8 Correct 500 ms 37864 KB Output is correct
9 Correct 444 ms 37492 KB Output is correct
10 Correct 461 ms 37964 KB Output is correct
11 Correct 463 ms 36936 KB Output is correct
12 Correct 440 ms 36752 KB Output is correct
13 Correct 445 ms 37300 KB Output is correct
14 Correct 549 ms 46568 KB Output is correct
15 Correct 456 ms 36656 KB Output is correct
16 Correct 609 ms 46876 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18012 KB Output is correct
2 Correct 26 ms 18396 KB Output is correct
3 Correct 27 ms 18388 KB Output is correct
4 Correct 26 ms 18396 KB Output is correct
5 Correct 28 ms 18372 KB Output is correct
6 Correct 28 ms 18700 KB Output is correct
7 Correct 27 ms 18412 KB Output is correct
8 Correct 28 ms 18772 KB Output is correct
9 Correct 29 ms 18552 KB Output is correct
10 Correct 37 ms 19112 KB Output is correct
11 Correct 37 ms 19148 KB Output is correct
12 Correct 37 ms 19100 KB Output is correct
13 Correct 37 ms 19104 KB Output is correct
14 Correct 39 ms 19560 KB Output is correct
15 Correct 37 ms 19184 KB Output is correct
16 Correct 19 ms 18012 KB Output is correct
17 Correct 91 ms 22184 KB Output is correct
18 Correct 560 ms 46552 KB Output is correct
19 Correct 521 ms 37028 KB Output is correct
20 Correct 510 ms 47648 KB Output is correct
21 Correct 559 ms 48672 KB Output is correct
22 Correct 625 ms 51264 KB Output is correct
23 Correct 500 ms 37864 KB Output is correct
24 Correct 444 ms 37492 KB Output is correct
25 Correct 461 ms 37964 KB Output is correct
26 Correct 463 ms 36936 KB Output is correct
27 Correct 440 ms 36752 KB Output is correct
28 Correct 445 ms 37300 KB Output is correct
29 Correct 549 ms 46568 KB Output is correct
30 Correct 456 ms 36656 KB Output is correct
31 Correct 609 ms 46876 KB Output is correct
32 Correct 4043 ms 165508 KB Output is correct
33 Correct 3651 ms 164264 KB Output is correct
34 Correct 3810 ms 168048 KB Output is correct
35 Correct 4117 ms 168028 KB Output is correct
36 Correct 3657 ms 166408 KB Output is correct
37 Correct 3794 ms 168672 KB Output is correct
38 Correct 5009 ms 240912 KB Output is correct
39 Correct 5198 ms 241012 KB Output is correct
40 Correct 3927 ms 177464 KB Output is correct
41 Correct 5034 ms 309584 KB Output is correct
42 Correct 5373 ms 311948 KB Output is correct
43 Correct 5296 ms 312008 KB Output is correct
44 Correct 5101 ms 240596 KB Output is correct