Submission #253401

#	Time	Username	Problem	Language	Result	Execution time	Memory
253401		iefnah06	Meetings (IOI18_meetings)	C++11	100 / 100	3196 ms	285780 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct line {
	int st, en;
	ll m, b;
	line() {}
	line(int st_, int en_, ll m_, ll b_) : st(st_), en(en_), m(m_), b(b_) {}
	ll eval(ll x){
		return m * x + b;
	}
};

vector<line> stuff;

struct line_container {
	int st, en;
	ll lazy;
	line_container(int st_, int en_) : st(st_), en(en_), lazy(0) {}

	line front(){
		assert(size());
		line l = stuff[st];
		l.b += lazy;
		return l;
	}

	line back(){
		assert(size());
		line l = stuff[en-1];
		l.b += lazy;
		return l;
	}

	ll eval_front(ll x){
		assert(size());
		return lazy + stuff[st].eval(x);
	}

	ll eval_back(ll x){
		assert(size());
		return lazy + stuff[en-1].eval(x);
	}

	ll at(int p){
		assert(size() > 0);
		int s = st, e = en;
		while(e - s > 1){
			int mid = (s + e) / 2;
			if(stuff[mid].st <= p){
				s = mid;
			} else {
				e = mid;
			}
		}
		assert(stuff[s].st <= p && p < stuff[s].en);
		return lazy + stuff[s].eval(p);
	}

	line pop_front(){
		assert(size());
		line l = stuff[st++];
		l.b += lazy;
		return l;
	}

	line pop_back(){
		assert(size());
		line l = stuff[--en];
		l.b += lazy;
		return l;
	}

	void push_back(line l){
		l.b -= lazy;
		stuff[en++] = l;
	}

	void push_front(line l){
		l.b -= lazy;
		stuff[--st] = l;
	}

	int size(){
		return en-st;
	}
};

int n;
int qnum;
vector<ll> ans;
vector<int> heights, ql, qr;
vector<pair<int, int> > key;

static const int S = 1 << 21;
vector<pair<pair<int, int>, int> > seg;

vector<vector<int> > queries;

pair<pair<int, int>, int> max_query(int l, int r){
	pair<pair<int, int>, int> res(make_pair(0, -1), -1);
	assert(max(0, l) < min(r, n));
	for(int a = S+l, b = S+r; a < b; a /= 2, b /= 2){
		if(a & 1){
			res = max(res, seg[a]);
			a++;
		}
		if(b & 1){
			--b;
			res = max(res, seg[b]);
		}
	}
	return res;
}

line_container solve(int l, int r){
	if(l >= r){
		return line_container(l, l);
	}
	int x = max_query(l, r).second;
	auto lcont = solve(l, x);
	auto rcont = solve(x+1, r);
	int cutoff = x+1;
	for(auto j : queries[x]){
		assert(l <= ql[j] && qr[j] < r);
		ll a;
		if(x == qr[j]){
			a = 0;
		} else if(x < qr[j]){
			a = rcont.at(qr[j]);
		} else assert(false);
		ll cnd = ll(x - ql[j] + 1) * heights[x] + a;
		ans[j] = min(ans[j], cnd);
	}
	rcont.lazy += heights[x] * ll(x - l + 1);
	if(lcont.size()){
		assert(lcont.back().en == x);
		ll lback = lcont.eval_back(x-1);
		while(rcont.size() > 0){
			assert(lcont.size());
			int st = rcont.front().st;
			int en = rcont.front().en;
			if(lback + (en - x) * ll(heights[x]) <= rcont.eval_front(en-1)){
				cutoff = en;
				rcont.pop_front();
				continue;
			}
			int s = st-1, e = en-1;
			while(e - s > 1){
				int mid = (s + e) / 2;
				ll lval = lback + (mid - x + 1) * ll(heights[x]);
				ll rval = rcont.eval_front(mid);
				if(lval > rval){
					e = mid;
				} else {
					s = mid;
				}
			}
			line bfront = rcont.pop_front();
			bfront.st = e;
			rcont.push_front(bfront);
			cutoff = e;
			break;
		}
		assert(x < cutoff);
		lcont.push_back(line(x, cutoff, heights[x], lback - ll(x-1) * heights[x]));
	} else {
		lcont.push_back(line(x, x+1, heights[x], -ll(x-1) * heights[x]));
	}
	if(lcont.size() > rcont.size()){
		while(rcont.size()){
			lcont.push_back(rcont.pop_front());
		}
		return lcont;
	} else {
		while(lcont.size()){
			rcont.push_front(lcont.pop_back());
		}
		return rcont;
	}
}

void solve(){
	for(int i = 0; i < n; i++){
		seg[S+i] = make_pair(key[i], i);
	}
	for(int i = S-1; i >= 1; i--){
		seg[i] = max(seg[2*i], seg[2*i+1]);
	}
	for(int i = 0; i < n; i++) queries[i].clear();
	for(int i = 0; i < qnum; i++){
		assert(ql[i] <= qr[i]);
		if(ql[i] < qr[i]){
			int x = max_query(ql[i], qr[i]+1).second;
			queries[x].push_back(i);
		}
	}
	solve(0, n);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
									 std::vector<int> R) {
	heights = H;
	ql = L;
	qr = R;
	n = int(heights.size());
	qnum = int(ql.size());
	ans.assign(qnum, 1e18);
	seg.resize(2*S);
	queries.resize(n);
	stuff.resize(n);
	for(int i = 0; i < qnum; i++){
		if(ql[i] == qr[i]){
			ans[i] = heights[ql[i]];
		}
	}
	key.resize(n);
	for(int i = 0; i < n; i++){
		key[i] = make_pair(heights[i], i);
	}
	for(int f = 0; f < 2; f++){
		solve();
		reverse(heights.begin(), heights.end());
		reverse(key.begin(), key.end());
		for(int i = 0; i < qnum; i++){
			ql[i] = n-1-ql[i];
			qr[i] = n-1-qr[i];
			swap(ql[i], qr[i]);
		}
	}
	return ans;
}

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