Submission #423296

#	Time	Username	Problem	Language	Result	Execution time	Memory
423296		amoo_safar	Meetings (IOI18_meetings)	C++17	19 / 100	54 ms	3436 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll Inf = 1e18;

const int N = 5e3 + 10;

int n, q;
vector<int> H, L, R;

ll dp[N], ans[N];
int par[N], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Merge(int u, int v, ll md){
	u = Find(u);
	v = Find(v);
	// cerr << "^^ " << sz[u] << ' ' << sz[v] << '\n';
	assert(u < v);
	// phase 1 
	for(int i = v - sz[v] + 1; i <= v; i++)
		dp[i] += 1ll * sz[u] * md;
	// phase 2
	for(int i = v - sz[v] + 1; i <= v; i++){
		if(dp[i] > dp[u] + md * (i - u))
			dp[i] =dp[u] + md * (i - u);
		else
			break;
	}
	sz[v] += sz[u];
	par[u] = v;
}

vector<int> Q[N];

void Solve(int rv){
	vector<int> ord(n, 0);

	iota(all(ord), 0);
	sort(all(ord), [&](int i, int j){
		// if(H[i] == H[j])
		return pii(H[i], rv * i) < pii(H[j], rv * j); 
	});
	
	fill(sz, sz + N, 1);
	iota(par,par +N, 0);
	fill(dp, dp + N, 0);
	for(int i = 0; i < N; i++) Q[i].clear();
	////////////////////////////

	for(int i = 0; i < q; i++){
		int idx = L[i];
		for(int j = L[i]; j <= R[i]; j++)
			if(pii(H[j], rv * j) > pii(H[idx], rv * idx))
				idx = j;
		Q[idx].pb(i);
	}

	for(int i : ord){
		for(int q_id : Q[i]){
			ans[q_id] = min(ans[q_id], 1ll * H[i] * (i - L[q_id] + 1) + dp[R[q_id] + 1]);
		}
		Merge(i, i + 1, H[i]);
		// cerr << "# " << i << '\n';
		// cerr << "!! ";
		// for(int i = 0; i <= n; i++)
		// 	cerr << dp[i] << ' ';
		// cerr << '\n';
	}
}

vector<long long> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R) {
	H = _H; L = _L; R = _R;
	n = H.size();
	q = L.size();

	
	fill(ans, ans + N, Inf);

	Solve(+1);
	
	reverse(all(H));
	for(auto &x : L) x = n - 1 - x;
	for(auto &x : R) x = n - 1 - x;
	L.swap(R);

	Solve(-1);
	vector<ll> ANS;
	for(int i = 0; i < q; i++)
		ANS.pb(ans[i]);
	return ANS;
}

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