Submission #597183

#	Time	Username	Problem	Language	Result	Execution time	Memory
597183		Lucpp	Meetings (IOI18_meetings)	C++17	36 / 100	5535 ms	9892 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
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;
}

struct Data{
	int pref, suff, ans, all;
	Data(int x=0):pref(x),suff(x),ans(x),all(x){}
};
Data combine(Data a, Data b){
	Data c;
	c.ans = max(a.ans, b.ans);
	c.ans = max(c.ans, a.suff+b.pref);
	if(a.all) c.pref = a.pref+b.pref;
	else c.pref = a.pref;
	if(b.all) c.suff = a.suff+b.suff;
	else c.suff = b.suff;
	c.all = a.all&b.all;
	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(2-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(l <= a && b <= r) return seg[i];
	if(b < l || r < a) return Data(0);
	int m = (a+b)/2;
	return combine(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
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);
	int 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++){
			C[i] = 2*(R[i]-L[i]+1) - qry(L[i]+1, R[i]+1).ans;
		}
	}
	return C;
}

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