제출 #425363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425363		amoo_safar	모임들 (IOI18_meetings)	C++17	41 / 100	679 ms	113468 KiB

meetings

#include "meetings.h"
 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
#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;
typedef pair<int, ll> pll;
 
const ll Inf = 1e18;
 
const int N = 75e4 + 10;
 
int n, q;
vector<int> H, L, R;
 
ll ans[N];
 
struct node {
	ll val_l, val_r;
	pll lz; // m h
	inline void Apply(pll &X, int L, int R){
		if(X.F > 0){
			val_l = L * X.F;
			val_r = (R - 1) * X.F;
			lz = {X.F, 0};
		}
		val_l += X.S;
		val_r += X.S;
		lz.S += X.S;
	}
};
node seg[N * 3];
 
inline void Shift(int id, int L, int R){
 	int mid = (L + R) >> 1;
 	seg[id << 1].Apply(seg[id].lz, L, mid);
 	seg[id<<1|1].Apply(seg[id].lz, mid, R);
	seg[id].lz = {0, 0};
}

void Add(int id, int l, int r, pll X, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		if((X.F == 0) || ((R - 1) * X.F + X.S <= seg[id].val_r)){
			seg[id].Apply(X, L, R);
			return ;
		} else if(seg[id].val_l <= L * X.F + X.S){
			return;
		}
	}

	int mid = (L + R) >> 1;
	Shift(id, L, R);
	Add(id << 1, l, r, X, L, mid);
	Add(id<<1|1, l, r, X, mid, R);

	seg[id].val_l = seg[id << 1].val_l;
	seg[id].val_r = seg[id << 1 | 1].val_r;
}

ll Get(int id, int idx, int L, int R){
	if(L + 1 == R) return seg[id].val_l;
	int mid = (L + R) >> 1;
	Shift(id, L, R);
	if(idx < mid)
		return Get(id << 1, idx, L, mid);
	return Get(id << 1 | 1, idx, mid, R);
}

// void Build(int id, int L, int R){
// 	seg[id].r = R - 1;
// 	if(L + 1 == R) return ;
// 	int mid = (L + R) >> 1;
// 	Build(id << 1, L, mid);
// 	Build(id<<1|1, mid, R);
// }
 
// int BS(int id, int l, int r, pll ln, int L, int R){
// 	if(r <= L || R <= l) return R;
	
// 	int mid = (L + R) >> 1;
	
// 	if(l <= L && R <= r){
// 		if(seg[id].val_r > 1ll * seg[id].r * ln.F + ln.S)
// 			return R;
// 		if(L + 1 == R)
// 			return L;
		
// 		Shift(id);
// 		int res = BS(id << 1, l, r, ln, L, mid);
// 		if(res < mid)
// 			return res;
// 		return BS(id << 1| 1, l, r, ln, mid, R);
// 	}
// 	Shift(id);
// 	int res = BS(id << 1, l, r, ln, L, mid);
// 	if(res < mid)
// 		return res;
// 	return BS(id<<1|1, l, r, ln, mid, R);
// }
 
 
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 
 
	Add(1, v - sz[v] + 1, v + 1, {0, 1ll * sz[u] * md}, 0, n + 1);
	// cerr << "!! " << 1ll * sz[u] * md << '\n';
	// for(int i = v - sz[v] + 1; i <= v; i++){
		// cerr << "&& " << Get(1, i, 0, n + 1) << '+' << 1ll*sz[u]*md << '=';
		// Add(1, i, i + 1, 1ll * sz[u] * md, 0, n + 1);
		// cerr << Get(1, i, 0, n + 1) << '\n';
		// if(Get(1, i, 0, n + 1) == 3){
		// 	cerr << "pr : ";
		// 	for(int i = n; i >= 0; i--)
		// 		cerr << Get(1, i, 0, n + 1) << ' ';
		// 	cerr << '\n';
		// }
	// }
		// dp[i] += 1ll * sz[u] * md;
	// phase 2
	ll vl_u = Get(1, u, 0, n + 1);
	Add(1, v - sz[v] + 1, v + 1, {md, vl_u - u * md}, 0, n + 1);
 
	// int lw = v - sz[v], hg = v + 1;
	// int bin_s = BS(1, lw + 1, hg, pll(md, vl_u - u * md), 0, n + 1);
 
	// while(lw + 1 < hg){
	// 	mid = (lw + hg) >> 1;
	// 	ll vl = Get(1, mid, 0, n + 1);
	// 	if(vl > vl_u + md * (mid - u))
	// 		lw = mid;
	// 	else 
	// 		hg = mid;
	// }
	// if(bin_s == n + 1)
	// 	bin_s = v + 1;
	// cerr << "! " << bin_s << ' ' << hg << '\n';
	// assert(bin_s == hg);
	// _ln = pll(md, vl_u - u * md);
	// Add_Line(1, v - sz[v] + 1, bin_s, 0, n + 1);
	// for(int i = v - sz[v] + 1; i <= v; i++){
	// 	ll vl = Get(1, i, 0, n + 1);
	// 	if(vl > vl_u + md * (i - u))
	// 		Add(1, i, i + 1, pll(0, vl_u + md * (i - u)), 0, n + 1);
	// 		// dp[i] =dp[u] + md * (i - u);
	// 	else
	// 		break;
	// }
	sz[v] += sz[u];
	par[u] = v;
}
 
vector<int> Q[N];
 
pii A[N];
pii sg[N << 2];
void BB(int id, int L, int R){
	if(L + 1 == R){
		sg[id] = A[L];
		return ;
	}
	int mid = (L + R) >> 1;
	BB(id << 1, L, mid);
	BB(id<<1|1, mid, R);
	sg[id] = max(sg[id << 1], sg[id << 1 | 1]);
}
pii GT(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return pii(-1, -1);
	if(l <= L && R <= r) return sg[id];
	int mid = (L + R) >> 1;
	return max(GT(id << 1, l, r, L, mid), GT(id << 1|1, l, r, mid, R));
}
 
// const int delta = 1e9;
 
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);
	// ll delta = 1e9;
	// _ln = {0, delta};
	// Add_Line(1, 0, n + 1, 0, n + 1);
	for(int i = 0; i < N*3; i++)
		seg[i].lz = {0, 0}, seg[i].val_l = seg[i].val_r = 0;

	for(int i = 0; i < N; i++) Q[i].clear();
	for(int i = 0; i < n; i++) A[i] = pii(H[i], rv * i);
	BB(1, 0, n);
	////////////////////////////
 
	for(int i = 0; i < q; i++){
		pii mx = GT(1, L[i], R[i] + 1, 0, n);
		int idx = mx.S / rv;
		// 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;
		// assert(idx == idx2);
		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) + Get(1, R[q_id] + 1, 0, n + 1));
		}
		Merge(i, i + 1, H[i]);
		// cerr << "# " << i << '\n';
		// cerr << "!! ";
		// for(int i = 0; i <= n; i++)
		// 	cerr << Get(1, i, 0, n + 1) << ' ';
		// 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();
 
	// Build(1, 0, n + 1);
	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<long long> ANS;
	for(int i = 0; i < q; i++)
		ANS.pb(ans[i]);
	return ANS;
}

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