제출 #248420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248420		kostia244	모임들 (IOI18_meetings)	C++17	0 / 100	45 ms	3532 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
int n, q, h[maxn], l[maxn], r[maxn], P[maxn];
vector<ll> ans;

array<int, 3> tree[2*maxn];
array<int, 3> merge(array<int, 3> a, array<int, 3> b) {
	if(a[0] ^ b[0]) return a[0] > b[0] ? a : b;
	return {a[0], min(a[1], b[1]), max(a[2], b[2])};
}
void upd(int p, int v) {
	p += n;
	for(tree[p] = {v, p-n, p-n}; p>>=1;) tree[p] = merge(tree[p<<1], tree[p<<1|1]);
}
array<int, 3> get(int l, int r) {
	//cout << l << " " << r << '\n';
	array<int, 3> res = {-1, 0, 0};
	for(l += n, r += n+1; l < r; l>>=1, r>>=1) {
		if(l&1) res = merge(res, tree[l++]);
		if(r&1) res = merge(res, tree[--r]);
	}
	//cout << res[0] << " " << res[1] << " " << res[2] << '\n';
	return res;
}

vector<ll> ma[21];
int N[21];
void upda(int t, int p, ll v) {
	for(ma[t][p+=N[t]] = v; p>>=1;) ma[t][p] = min(ma[t][p<<1], ma[t][p<<1|1]);
}
ll geta(int t, ll l, ll r) {
	ll ans = 1ll<<55;
	for(l += N[t], r += N[t]+1; l < r; l>>=1, r>>=1) {
		if(l&1) ans = min(ans, ma[t][l++]);
		if(r&1) ans = min(ans, ma[t][--r]);
	}
	return ans;
}

map<pair<int, int>, ll> memo;
ll solve(int l, int r) {
	if(r < l) return 0;
	if(memo.count({l, r})) return memo[{l, r}];
	auto [V, tl, tr] = get(l, r);
	ll ans = min({V*1ll*(r-tl+1) + solve(l, tl-1), V*1ll*(tr-l+1) + solve(tr+1, r), V*1ll*(r-l+1) + geta(V, P[tl], P[tr]-1)});
	//cout << l << " " << r << " " << V << " " << tl << " " << tr << " / " << ans << '\n';
	return memo[{l, r}] = ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	q = L.size();
	n = H.size();
	for(int i = 0; i < n; i++) {
		h[i] = H[i];
		l[i] = L[i];
		r[i] = R[i];
	}
	ans.resize(q);
	for(int i = 0; i < n; i++) upd(i, h[i]);
	vector<int> lst(22, -1);
	for(int i = 0; i < n; i++) N[h[i]]++;
	for(int i = 1; i <= 20; i++) ma[i].resize(2*N[i]);
	vector<int> tcnt(22, 0);
	for(int i = 0; i < n; i++) {
		P[i] = tcnt[h[i]]++;
		if(lst[h[i]] != -1) {
			upda(h[i], P[i], solve(lst[h[i]]+1, i-1) - h[i]*1ll*(i - lst[h[i]] - 1));
		}
		lst[h[i]] = i;
	}
	for(int i = 0; i < q; i++) ans[i] = solve(l[i], r[i]);
	return ans;
}

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