oj.uz

Submission #108319

# Submission time Handle Problem Language Result Execution time Memory
108319 2019-04-28T14:00:24 Z Noam527 Meetings (IOI18_meetings) C++17
100 / 100
 5499 ms 312024 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);
	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]);
		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 (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]));
		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 (prev != -1 && prev < v) {
		for (const auto &i : Q[prev]) {
			if (prev < i.r)
				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);
	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);
	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:201:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17908 KB Output is correct
2 Correct 26 ms 18424 KB Output is correct
3 Correct 27 ms 18396 KB Output is correct
4 Correct 26 ms 18456 KB Output is correct
5 Correct 26 ms 18392 KB Output is correct
6 Correct 27 ms 18632 KB Output is correct
7 Correct 26 ms 18372 KB Output is correct
8 Correct 28 ms 18808 KB Output is correct
9 Correct 28 ms 18636 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17908 KB Output is correct
2 Correct 26 ms 18424 KB Output is correct
3 Correct 27 ms 18396 KB Output is correct
4 Correct 26 ms 18456 KB Output is correct
5 Correct 26 ms 18392 KB Output is correct
6 Correct 27 ms 18632 KB Output is correct
7 Correct 26 ms 18372 KB Output is correct
8 Correct 28 ms 18808 KB Output is correct
9 Correct 28 ms 18636 KB Output is correct
10 Correct 37 ms 19192 KB Output is correct
11 Correct 37 ms 19104 KB Output is correct
12 Correct 37 ms 19100 KB Output is correct
13 Correct 36 ms 19140 KB Output is correct
14 Correct 39 ms 19612 KB Output is correct
15 Correct 36 ms 19084 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18040 KB Output is correct
2 Correct 89 ms 22244 KB Output is correct
3 Correct 569 ms 46492 KB Output is correct
4 Correct 518 ms 37060 KB Output is correct
5 Correct 508 ms 47740 KB Output is correct
6 Correct 565 ms 48676 KB Output is correct
7 Correct 625 ms 51284 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18040 KB Output is correct
2 Correct 89 ms 22244 KB Output is correct
3 Correct 569 ms 46492 KB Output is correct
4 Correct 518 ms 37060 KB Output is correct
5 Correct 508 ms 47740 KB Output is correct
6 Correct 565 ms 48676 KB Output is correct
7 Correct 625 ms 51284 KB Output is correct
8 Correct 483 ms 37896 KB Output is correct
9 Correct 441 ms 37576 KB Output is correct
10 Correct 456 ms 37948 KB Output is correct
11 Correct 485 ms 36936 KB Output is correct
12 Correct 452 ms 36764 KB Output is correct
13 Correct 450 ms 37300 KB Output is correct
14 Correct 556 ms 46604 KB Output is correct
15 Correct 454 ms 36668 KB Output is correct
16 Correct 615 ms 46832 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17908 KB Output is correct
2 Correct 26 ms 18424 KB Output is correct
3 Correct 27 ms 18396 KB Output is correct
4 Correct 26 ms 18456 KB Output is correct
5 Correct 26 ms 18392 KB Output is correct
6 Correct 27 ms 18632 KB Output is correct
7 Correct 26 ms 18372 KB Output is correct
8 Correct 28 ms 18808 KB Output is correct
9 Correct 28 ms 18636 KB Output is correct
10 Correct 37 ms 19192 KB Output is correct
11 Correct 37 ms 19104 KB Output is correct
12 Correct 37 ms 19100 KB Output is correct
13 Correct 36 ms 19140 KB Output is correct
14 Correct 39 ms 19612 KB Output is correct
15 Correct 36 ms 19084 KB Output is correct
16 Correct 19 ms 18040 KB Output is correct
17 Correct 89 ms 22244 KB Output is correct
18 Correct 569 ms 46492 KB Output is correct
19 Correct 518 ms 37060 KB Output is correct
20 Correct 508 ms 47740 KB Output is correct
21 Correct 565 ms 48676 KB Output is correct
22 Correct 625 ms 51284 KB Output is correct
23 Correct 483 ms 37896 KB Output is correct
24 Correct 441 ms 37576 KB Output is correct
25 Correct 456 ms 37948 KB Output is correct
26 Correct 485 ms 36936 KB Output is correct
27 Correct 452 ms 36764 KB Output is correct
28 Correct 450 ms 37300 KB Output is correct
29 Correct 556 ms 46604 KB Output is correct
30 Correct 454 ms 36668 KB Output is correct
31 Correct 615 ms 46832 KB Output is correct
32 Correct 4051 ms 165556 KB Output is correct
33 Correct 3727 ms 164292 KB Output is correct
34 Correct 3814 ms 167980 KB Output is correct
35 Correct 4058 ms 168020 KB Output is correct
36 Correct 3718 ms 166416 KB Output is correct
37 Correct 3790 ms 168668 KB Output is correct
38 Correct 4941 ms 240980 KB Output is correct
39 Correct 5174 ms 240984 KB Output is correct
40 Correct 3913 ms 177376 KB Output is correct
41 Correct 5117 ms 309596 KB Output is correct
42 Correct 5499 ms 312024 KB Output is correct
43 Correct 5308 ms 312020 KB Output is correct
44 Correct 5095 ms 240620 KB Output is correct