oj.uz

Submission #769328

# Submission time Handle Problem Language Result Execution time Memory
769328 2023-06-29T12:25:56 Z SanguineChameleon Meetings (IOI18_meetings) C++17
100 / 100
 2429 ms 560436 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

struct query {
	int id = 0;
	int pos = 0;
	long long off = 0;

	query(int _id, int _pos, long long _off): id(_id), pos(_pos), off(_off) {};
};

struct node {
	int pos = 0;
	int rangeL = 0;
	int rangeR = 0;
	int sz = 0;
	long long off = 0;
	node *left = nullptr;
	node *right = nullptr;
	vector<query> queries;

	node(int _pos, int _rangeL, int _rangeR, node *_left, node *_right): pos(_pos), rangeL(_rangeL), rangeR(_rangeR), left(_left), right(_right) {};
};

struct line {
	int lt = 0;
	int rt = 0;
	long long a = 0;
	long long b = 0;

	line(int _lt, int _rt, long long _a, long long _b): lt(_lt), rt(_rt), a(_a), b(_b) {};

	long long eval(int x) {
		return a * (x - lt) + b;
	}
};

const long long inf = 1e18L + 20;
const int maxN = 7.5e5 + 20;
const int maxK = 20;
int lg[maxN];
pair<pair<int, int>, int> sparse[maxN][maxK];
pair<int, int> H[maxN];
node *nodes[maxN];
int L[maxN];
int R[maxN];
vector<long long> res;
int N, Q;

int get(int lt, int rt) {
	int k = lg[rt - lt + 1];
	return max(sparse[lt][k], sparse[rt - (1 << k) + 1][k]).second;
}

node *build(int lt, int rt) {
	if (lt > rt) {
		return nullptr;
	}
	int mx = get(lt, rt);
	nodes[mx] = new node(mx, lt, rt, build(lt, mx - 1), build(mx + 1, rt));
	return nodes[mx];
}

map<int, line*> lines;

void calc(node *cur) {
	long long left_cost = 0;
	if (cur->left) {
		calc(cur->left);
		cur->off = cur->left->off;
		cur->sz = cur->left->sz;
		left_cost = prev(lines.upper_bound(cur->pos - 1))->second->eval(cur->pos - 1) + cur->left->off;
	}
	cur->sz++;
	line *mid = new line(cur->pos, cur->rangeR, H[cur->pos].first, left_cost + H[cur->pos].first - cur->off);
	lines[cur->pos] = mid;
	if (cur->right) {
		calc(cur->right);
		cur->right->off += 1LL * H[cur->pos].first * (cur->pos - cur->rangeL + 1);
		auto it = next(lines.find(cur->pos));
		while (it != lines.end() && it->first <= cur->rangeR) {
			if (mid->eval(it->second->rt) + cur->off <= it->second->eval(it->second->rt) + cur->right->off) {
				it = lines.erase(it);
				cur->right->sz--;
			}
			else {
				break;
			}
		}
		if (it != lines.end() && it->first <= cur->rangeR) {
			int lt = it->second->lt;
			int rt = it->second->rt - 1;
			int last = lt - 1;
			while (lt <= rt) {
				int mt = (lt + rt) / 2;
				if (mid->eval(mt) + cur->off <= it->second->eval(mt) + cur->right->off) {
					last = mt;
					lt = mt + 1;
				}
				else {
					rt = mt - 1;
				}
			}
			mid->rt = last;
			if (mid->rt + 1 > it->second->lt) {
				it->second->b = it->second->eval(mid->rt + 1);
				it->second->lt = mid->rt + 1;
				lines[it->second->lt] = it->second;
				it = lines.erase(it);
			}
		}
		if (cur->sz >= cur->right->sz) {
			while (it != lines.end() && it->first <= cur->rangeR) {
				it->second->b -= cur->off - cur->right->off;
				it++;
			}
		}
		else {
			it = lines.find(cur->rangeL);
			while (it != lines.end() && it->first <= cur->pos) {
				it->second->b -= cur->right->off - cur->off;
				it++;
			}
			cur->off = cur->right->off;
		}
		cur->sz += cur->right->sz;
	}
	for (auto q: cur->queries) {
		res[q.id] = min(res[q.id], prev(lines.upper_bound(q.pos))->second->eval(q.pos) + cur->off + q.off);
	}
}

void solve() {
	for (int i = 0; i < N; i++) {
		sparse[i][0] = make_pair(H[i], i);
	}
	for (int k = 1; k < maxK; k++) {
		for (int i = 0; i + (1 << k) <= N; i++) {
			sparse[i][k] = max(sparse[i][k - 1], sparse[i + (1 << (k - 1))][k - 1]);
		}
	}
	node *root = build(0, N - 1);
	for (int i = 0; i < Q; i++) {
		int mx = get(L[i], R[i]);
		res[i] = min(res[i], 1LL * H[mx].first * (R[i] - L[i] + 1));
		if (mx < R[i]) {
			nodes[mx]->right->queries.emplace_back(i, R[i], 1LL * H[mx].first * (mx - L[i] + 1));
		}
	}
	lines.clear();
	calc(root);
}

vector<long long> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R) {
	for (int i = 2; i < maxN; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	N = _H.size();
	for (int i = 0; i < N; i++) {
		H[i] = make_pair(_H[i], i);
	}
	Q = _L.size();
	for (int i = 0; i < Q; i++) {
		L[i] = _L[i];
		R[i] = _R[i];
	}
	res.resize(Q, inf);
	for (int iter = 0; iter < 2; iter++) {
		solve();
		reverse(H, H + N);
		for (int i = 0; i < Q; i++) {
			L[i] = N - 1 - L[i];
			R[i] = N - 1 - R[i];
			swap(L[i], R[i]);
		}
	}
	return res;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3176 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4692 KB Output is correct
4 Correct 4 ms 4692 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 4704 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3176 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4692 KB Output is correct
4 Correct 4 ms 4692 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 4704 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct
10 Correct 7 ms 6124 KB Output is correct
11 Correct 7 ms 6196 KB Output is correct
12 Correct 8 ms 6228 KB Output is correct
13 Correct 7 ms 6196 KB Output is correct
14 Correct 8 ms 6740 KB Output is correct
15 Correct 6 ms 6212 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 31 ms 11596 KB Output is correct
3 Correct 177 ms 70724 KB Output is correct
4 Correct 143 ms 61044 KB Output is correct
5 Correct 138 ms 67020 KB Output is correct
6 Correct 150 ms 69936 KB Output is correct
7 Correct 180 ms 71872 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 31 ms 11596 KB Output is correct
3 Correct 177 ms 70724 KB Output is correct
4 Correct 143 ms 61044 KB Output is correct
5 Correct 138 ms 67020 KB Output is correct
6 Correct 150 ms 69936 KB Output is correct
7 Correct 180 ms 71872 KB Output is correct
8 Correct 155 ms 64268 KB Output is correct
9 Correct 150 ms 63420 KB Output is correct
10 Correct 159 ms 64332 KB Output is correct
11 Correct 150 ms 61312 KB Output is correct
12 Correct 155 ms 60428 KB Output is correct
13 Correct 143 ms 61832 KB Output is correct
14 Correct 175 ms 72392 KB Output is correct
15 Correct 126 ms 60492 KB Output is correct
16 Correct 199 ms 68900 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3176 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4692 KB Output is correct
4 Correct 4 ms 4692 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 4704 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct
10 Correct 7 ms 6124 KB Output is correct
11 Correct 7 ms 6196 KB Output is correct
12 Correct 8 ms 6228 KB Output is correct
13 Correct 7 ms 6196 KB Output is correct
14 Correct 8 ms 6740 KB Output is correct
15 Correct 6 ms 6212 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 31 ms 11596 KB Output is correct
18 Correct 177 ms 70724 KB Output is correct
19 Correct 143 ms 61044 KB Output is correct
20 Correct 138 ms 67020 KB Output is correct
21 Correct 150 ms 69936 KB Output is correct
22 Correct 180 ms 71872 KB Output is correct
23 Correct 155 ms 64268 KB Output is correct
24 Correct 150 ms 63420 KB Output is correct
25 Correct 159 ms 64332 KB Output is correct
26 Correct 150 ms 61312 KB Output is correct
27 Correct 155 ms 60428 KB Output is correct
28 Correct 143 ms 61832 KB Output is correct
29 Correct 175 ms 72392 KB Output is correct
30 Correct 126 ms 60492 KB Output is correct
31 Correct 199 ms 68900 KB Output is correct
32 Correct 1377 ms 438740 KB Output is correct
33 Correct 1130 ms 436032 KB Output is correct
34 Correct 1299 ms 445636 KB Output is correct
35 Correct 1526 ms 445460 KB Output is correct
36 Correct 1130 ms 439360 KB Output is correct
37 Correct 1365 ms 448220 KB Output is correct
38 Correct 2085 ms 528776 KB Output is correct
39 Correct 2135 ms 528768 KB Output is correct
40 Correct 1681 ms 475808 KB Output is correct
41 Correct 2228 ms 557896 KB Output is correct
42 Correct 2358 ms 560436 KB Output is correct
43 Correct 2429 ms 560384 KB Output is correct
44 Correct 2272 ms 493980 KB Output is correct