Submission #769328

#	Time	Username	Problem	Language	Result	Execution time	Memory
769328		SanguineChameleon	Meetings (IOI18_meetings)	C++17	100 / 100	2429 ms	560436 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40