Submission #368110

#	Time	Username	Problem	Language	Result	Execution time	Memory
368110		Akashi	Meetings (IOI18_meetings)	C++14	100 / 100	3044 ms	325136 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

const int DIM = 750005;
const long long INF = 1e18;

int n;
int val[DIM];

struct Line {
	long long a, b;
	Line(long long _a = 0, long long _b = 0) {a = _a; b = _b;}
	long long get(int t) {
		return 1LL * a * t + b;
	}
};

struct SegTree {
	long long lazy[4 * DIM];
	Line line[4 * DIM];

	void build(int st = 1, int dr = n, int nod = 1) {
		lazy[nod] = 0; line[nod] = {0, INF};
		if (st == dr) {line[nod] = {0, 0}; return ;} 
		build(st, (st + dr) / 2, nod * 2);
		build((st + dr) / 2 + 1, dr, nod * 2 + 1);
	}

	void upd(int nod, long long val) {
		lazy[nod] += val;
		line[nod].b += val;
	}

	void propag(int nod) {
		if (lazy[nod] == 0) return ;
		for (int i = nod * 2; i <= nod * 2 + 1 ; ++i) upd(i, lazy[nod]);	
		lazy[nod] = 0;
	}

	long long query(int x, int st = 1, int dr = n, int nod = 1) {
		if (st == dr) return line[nod].get(x);
		propag(nod);
		int mij = (st + dr) / 2;
		if (x <= mij) return min(line[nod].get(x), query(x, st, mij, nod * 2));
		return min(line[nod].get(x), query(x, mij + 1, dr, nod * 2 + 1));
	}

	void update(int x, int y, long long val, int st = 1, int dr = n, int nod = 1) {
		if (x <= st && dr <= y) {upd(nod, val); return ;}
		propag(nod);
		int mij = (st + dr) / 2;
		if (x <= mij) update(x, y, val, st, mij, nod * 2);
		if (mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
	}

	void idk(int l, int r, Line newLine, int st = 1, int dr = n, int nod = 1) {
		if (l <= st && dr <= r) {
			long long A = newLine.get(st), B = line[nod].get(st), C = newLine.get(dr), D = line[nod].get(dr);
			if (A <= B && C <= D) {line[nod] = newLine; return ;}
			if (A >= B && C >= D) return ;

			propag(nod);
			int mij = (st + dr) / 2;
			if (A <= B) swap(line[nod], newLine);

			if (line[nod].get(mij) <= newLine.get(mij)) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
			else swap(line[nod], newLine), idk(l, r, newLine, st, mij, nod * 2);
			return ;
		}

		propag(nod);
		int mij = (st + dr) / 2;
		if (l <= mij) idk(l, r, newLine, st, mij, nod * 2);
		if (mij + 1 <= r) idk(l, r, newLine, mij + 1, dr, nod * 2 + 1);
	}

	void merge(int l, int split, int r, int tip) {
		if (tip == 0) {
			long long aux = query(split - 1);
			Line newLine = {val[split], aux - 1LL * (split - 1) * val[split]};
			idk(split, r, newLine);
		} else {
			long long aux = query(split + 1);
			Line newLine = {-val[split], aux + 1LL * (split + 1) * val[split]};
			idk(l, split, newLine); 
		}
	}
};

SegTree L, R;

struct query {
	int l, r, ind;
};

vector <long long> ans;
vector <query> myQ[DIM];

pair <int, int> arb[4 * DIM];
pair <int, int> max(pair <int, int> a, pair <int, int> b) {
	if (a.first > b.first || (a.first == b.first && a.second < b.second)) return a;
	return b;
}
void build_max(int st = 1, int dr = n, int nod = 1) {
	if (st == dr) {arb[nod] = {val[st], st}; return ;}
	int mij = (st + dr) / 2;
	build_max(st, mij, nod * 2);
	build_max(mij + 1, dr, nod * 2 + 1);
	arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

pair <int, int> _get_max(int x, int y, int st = 1, int dr = n, int nod = 1) {
	if (x <= st && dr <= y) return arb[nod];
	pair <int, int> ans = {-1, -1}; int mij = (st + dr) / 2;
	if (x <= mij) ans = max(ans, _get_max(x, y, st, mij, nod * 2));
	if (mij + 1 <= y) ans = max(ans, _get_max(x, y, mij + 1, dr, nod * 2 + 1));
	return ans;
}

int get_max(int x, int y) {
	return _get_max(x, y).second;
}

void solve(int l, int r) {
	if (l > r) return ;
	int split = get_max(l, r);

	solve(l, split - 1);
	solve(split + 1, r);

	for (auto it : myQ[split]) 
	ans[it.ind] = min(L.query(it.r) + 1LL * (split - it.l + 1) * val[split], R.query(it.l) + 1LL * (it.r - split + 1) * val[split]);
	
	L.update(split, r, 1LL * val[split] * (split - l + 1));
	if (split != l) L.merge(l, split, r, 0);

	R.update(l, split, 1LL * val[split] * (r - split + 1));
	if (split != r) R.merge(l, split, r, 1);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> LQ,
                                     std::vector<int> RQ) {
	n = (int)H.size();
	for (int i = 1; i <= n ; ++i) val[i] = H[i - 1];
	build_max();

	int Q = (int)LQ.size();
	ans.resize(Q);
	for (int i = 0; i < Q ; ++i) myQ[get_max(LQ[i] + 1, RQ[i] + 1)].push_back({LQ[i] + 1, RQ[i] + 1, i});

	L.build(); R.build();
	solve(1, n);
  return ans;
}

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