Submission #597512

#	Time	Username	Problem	Language	Result	Execution time	Memory
597512		Lucpp	Meetings (IOI18_meetings)	C++17	19 / 100	5576 ms	68752 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll solve(int n, vector<int> H){
	vector<ll> ans(n);
	ll v = 0;
	stack<pair<ll, int>> st;
	for(int i = 0; i < n; i++){
		int j = i;
		while(!st.empty() && st.top().first < H[i]){
			v -= st.top().first * st.top().second;
			j -= st.top().second;
			st.pop();
		}
		v += ll(H[i])*(i-j);
		ans[i] += v;
		v += H[i];
		if(!st.empty() && st.top().first == H[i]) st.top().second += i+1-j;
		else st.emplace(H[i], i+1-j);
	}
	v = 0;
	st = stack<pair<ll, int>>();
	for(int i = n-1; i >= 0; i--){
		ans[i] += v;
		int j = i;
		while(!st.empty() && st.top().first < H[i]){
			v -= st.top().first * st.top().second;
			j += st.top().second;
			st.pop();
		}
		v += ll(H[i])*(j+1-i);
		if(!st.empty() && st.top().first == H[i]) st.top().second += j+1-i;
		else st.emplace(H[i], j+1-i);
	}
	ll mi = INF;
	for(int i = 0; i < n; i++) mi = min(mi, ans[i]+H[i]);
	return mi;
}

int maxH = 20;

struct Data{
	int mi;
	vector<pair<int, int>> pref, suff;
	vector<int> le, ri;
	bool id;
	Data(int x=-1){
		if(x == -1) id = true;
		else{
			id = false;
			pref.emplace_back(x, 1);
			suff.emplace_back(x, 1);
			le.assign(maxH, 0);
			ri.assign(maxH, 0);
			le[x] = ri[x] = x;
			mi = x;
		}
	}
};
Data combine(Data a, Data b){
	if(a.id) return b;
	if(b.id) return a;
	Data c;
	c.id = false;

	int i = sz(b.pref)-1, dis = 0;
	for(auto [h, d] : b.pref) dis += d;
	int add = 0;
	vector<int> toAdd(maxH);
	for(int j = 0; j < maxH; j++){
		while(i >= 0 && b.pref[i].first <= j){
			add += b.pref[i].first*b.pref[i].second;
			dis -= b.pref[i].second;
			i--;
		}
		toAdd[j] = add + dis*j;
	}
	for(int j = 0; j < maxH; j++) a.ri[j] += toAdd[j];
	for(int j = 0; j < maxH; j++) a.le[j] += toAdd[a.mi];

	i = sz(a.suff)-1, dis = 0;
	for(auto [h, d] : a.suff) dis += d;
	add = 0;
	toAdd.assign(maxH, 0);
	for(int j = 0; j < maxH; j++){
		while(i >= 0 && a.suff[i].first <= j){
			add += a.suff[i].first*a.suff[i].second;
			dis -= a.suff[i].second;
			i--;
		}
		toAdd[j] = add + dis*j;
	}
	for(int j = 0; j < maxH; j++) b.le[j] += toAdd[j];
	for(int j = 0; j < maxH; j++) b.ri[j] += toAdd[b.mi];

	c.le = a.le;
	c.ri = b.ri;
	c.mi = min(a.mi, b.mi);
	for(int j = 0; j < maxH; j++){
		c.le[min(j, a.mi)] = max(c.le[min(j, a.mi)], b.le[j]);
	}
	for(int j = 0; j < maxH; j++){
		c.ri[min(j, b.mi)] = max(c.ri[min(j, b.mi)], a.ri[j]);
	}

	c.pref = a.pref;
	for(i = 0; i < sz(b.pref); i++){
		if(b.pref[i].first >= c.pref.back().first) c.pref.back().second += b.pref[i].second;
		else c.pref.push_back(b.pref[i]);
	}
	c.suff = b.suff;
	for(i = 0; i < sz(a.suff); i++){
		if(a.suff[i].first > c.suff.back().first) c.suff.back().second += a.suff[i].second;
		else c.suff.push_back(a.suff[i]);
	}
	return c;
}
int cap;
vector<Data> seg;
void init(vector<int> h){
	int n = int(h.size());
	for(cap=1; cap < n; cap*=2);
	seg.resize(2*cap);
	for(int i = 0; i < n; i++) seg[i+cap] = Data(maxH-h[i]);
	for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
}
Data qry(int l, int r, int a, int b, int i){
	if(b < l || r < a) return Data(-1);
	// int ans = max(*max_element(seg[i].le.begin(), seg[i].le.end()), *max_element(seg[i].ri.begin(), seg[i].ri.end()));
	// cerr << a << " " << b << "   " << ans << "\n";
	if(l <= a && b <= r) return seg[i];
	int m = (a+b)/2;
	Data d = combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
	return d;
}
Data qry(int l, int r){return qry(l, r, 1, cap, 1);}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = (int)L.size();
	vector<ll> C(Q);
	maxH = *max_element(H.begin(), H.end());
	if(maxH > 2){
		for(int j = 0; j < Q; ++j){
			vector<int> h;
			for(int k = L[j]; k <= R[j]; k++) h.push_back(H[k]);
			C[j] = solve((int)h.size(), h);
		}
	}
	else{
		init(H);
		for(int i = 0; i < Q; i++){
			Data d = qry(L[i]+1, R[i]+1);
			int ans = max(*max_element(d.le.begin(), d.le.end()), *max_element(d.ri.begin(), d.ri.end()));
			C[i] = maxH*(R[i]-L[i]+1) - ans;
		}
	}
	return C;
}

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