Submission #818030

#	Time	Username	Problem	Language	Result	Execution time	Memory
818030		sofapuden	Meetings (IOI18_meetings)	C++14	0 / 100	168 ms	6020 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

vector<vector<int>> bitl, bitr, sparse;
vector<vector<ll>> vall, valr;
vector<int> h;

ll c(int l, int r, int x){
	if(x > r || x < l)return (1ll<<60);
	int cul = x;
	ll ans = -h[x];
	for(int i = 18; ~i; --i){
		if(bitl[i][cul] >= l){
			ans+=vall[i][cul];
			cul = bitl[i][cul];
		}
	}
	ans += (cul - l + 1) * h[cul];
	int cur = x;
	for(int i = 18; ~i; --i){
		if(bitr[i][cur] <= r){
			ans+=valr[i][cur];
			cur = bitr[i][cur];
		}
	}
	ans += (r - cur + 1) * h[cur];
	return ans;
}

int merge(int l, int r){
	int cnt = (r > l + 1 ? 31 - __builtin_clz(r - l - 1) : 0);
	int k = (1<<cnt);
	ll val = (1ll << 60);
	int id = 0;
	ll z = c(l,r,sparse[cnt][l]);
	if(z < val)id = sparse[cnt][l], val = z;
	z = c(l,r,sparse[cnt][r - k]);
	if(z < val)id = sparse[cnt][r - k], z = val;
	z = c(l,r,l+k);
	if(z < val)id = l + k, z = val;
	z = c(l,r,r - k);
	if(z < val)id = r - k, z = val;
	z = c(l,r,l+k+1);
	if(z < val)id = l + k+1, z = val;
	z = c(l,r,r - k-1);
	if(z < val)id = r - k-1, z = val;
	return id;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	h = H;
	int n = H.size();
	int q = L.size();
	vector<int> pl, pr;
	vector<int> cu;
	for(int i = 0; i < n; ++i){
		while(cu.size() && H[cu.back()] <= H[i])cu.pop_back();
		pl.push_back(cu.size() ? cu.back() : i);
		cu.push_back(i);
	}
	cu.clear();
	for(int i = n-1; ~i; --i){
		while(cu.size() && H[cu.back()] <= H[i])cu.pop_back();
		pr.push_back(cu.size() ? cu.back() : i);
		cu.push_back(i);
	}
	reverse(pr.begin(),pr.end());
	bitl.resize(19, vector<int>(n));
	bitr.resize(19, vector<int>(n));
	sparse.resize(19, vector<int>(n));
	vall.resize(19, vector<ll>(n));
	valr.resize(19, vector<ll>(n));
	for(int i = 0; i < n; ++i){
		bitl[0][i] = pl[i];
		vall[0][i] = 1ll * (i - pl[i]) * H[i];
	}
	for(int i = 0; i < n; ++i){
		bitr[0][i] = pr[i];
		valr[0][i] = 1ll * (pr[i] - i) * H[i];
	}
	for(int i = 1; i < 19; ++i){
		for(int j = 0; j < n; ++j){
			bitl[i][j] = bitl[i-1][bitl[i-1][j]];
			vall[i][j] = vall[i-1][bitl[i-1][j]] + vall[i-1][j];
			bitr[i][j] = bitr[i-1][bitr[i-1][j]];
			valr[i][j] = valr[i-1][bitr[i-1][j]] + valr[i-1][j];
		}
	}

	iota(sparse[0].begin(),sparse[0].end(),0);
	for(int i = 1; i < 19; ++i){
		for(int j = 0; j < n; ++j){
			if(j + (1<<(i - 1)) >= n)break;
			sparse[i][j] = merge(j, j + (1 << (i-1)));
		}
	}
	vector<ll> ans;
	for(int i = 0; i < q; ++i){
		if(L[i] == R[i])ans.push_back(H[L[i]]);
		else ans.push_back(c(L[i],R[i],merge(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