Submission #1229900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229900		AmirAli_H1	Meetings (IOI18_meetings)	C++17	21 / 100	232 ms	139556 KiB

meetings

// In the name of Allah

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 20) + 4;
const int maxs = (1 << 21) + 4;
const int maxlg = 20;
const ll oo = 1e18 + 4;

int n, q;
pll A[maxn]; int L[maxn], R[maxn];
pll rmq[maxn][maxlg]; pii Qx[maxn]; vector<ll> ans;
pii Q1[maxn], Q2[maxn]; ll val1[maxn], val2[maxn];
vector<pair<int, pii>> ls; ll dp[maxs];
ll valx[maxn], valr[maxn], vals[maxn], valf[maxn];
vector<int> adj[maxn]; int h[maxn], par[maxn], sz[maxn];
int st[maxn], ft[maxn], timer, ind[maxn], hld[maxn];
vector<pair<int, pii>> Q[maxn]; set<int> stx;
vector<int> lsx[maxn], vc;

int GI(int l, int r) {
	pair<int, pii> x = Mp(r - l, Mp(l, r));
	int j = lower_bound(all(ls), x) - ls.begin();
	if (j < len(ls) && ls[j] == x) return j;
	return -1;
}

void build_rmq() {
	for (int i = n - 1; i >= 0; i--) {
		rmq[i][0] = A[i];
		for (int j = 1; j < maxlg; j++) {
			if (i + (1 << j) - 1 >= n) break;
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
}

pll get_max(int l, int r) {
	if (l >= r) return Mp(-oo, -1);
	int j = __lg(r - l);
	return max(rmq[l][j], rmq[r - (1 << j)][j]);
}

void pre_dfs(int v, int p = -1) {
	par[v] = p; sz[v] = 1;
	for (int u : adj[v]) {
		h[u] = h[v] + 1;
		pre_dfs(u, v);
		sz[v] += sz[u];
	}
}

bool cmp(int i, int j) {
	return (sz[i] > sz[j]);
}

void res_dfs(int v, int p = -1) {
	st[v] = timer++; ind[st[v]] = v;
	if (p != -1 && st[p] + 1 == st[v]) hld[v] = hld[p];
	else hld[v] = v;
	sort(all(adj[v]), cmp);
	for (int u : adj[v]) {
		res_dfs(u, v);
	}
	ft[v] = timer;
}

void cal_val(int v, int r, int x, int i) {
	while (h[v] > h[r]) {
		int u = hld[v];
		if (h[u] > h[r]) {
			Q[v].pb(Mp(u, Mp(x, i)));
			v = par[u];
		}
		else {
			Q[v].pb(Mp(ind[st[r] + 1], Mp(x, i)));
			v = r;
		}
	}
}

ll calx(int i, int x) {
	return valf[i] - A[i].F * x;
}

void checkx(int i, int j, int x) {
	ll R1 = calx(i, x), R2 = calx(j, x);
	if (R2 >= R1) {
		int f = upper_bound(all(vc), x) - vc.begin() - 1;
		if (f >= 0) lsx[f].pb(j);
	}
	else if (A[i].F != A[j].F) {
		ll w = (A[j].F - A[i].F);
		ll Rx = ((R1 - R2) + (w - 1)) / w;
		int f = upper_bound(all(vc), max(-1ll, x - Rx)) - vc.begin() - 1;
		if (f >= 0) lsx[f].pb(j);
	}
}

void addx(int i) {
	if (stx.empty()) {
		stx.insert(i);
		return ;
	}
	int j = *stx.begin(), x = i;
	checkx(i, j, x);
	stx.insert(i);
}

void delx(int i, int x) {
	if (stx.find(i) == stx.end()) return ;
	stx.erase(i);
	auto it = stx.lower_bound(i);
	if (it == stx.begin() || it == stx.end()) return ;
	int j = *it; it--; i = *it;
	checkx(i, j, x);
}

ll getx(int j, int x) {
	ll ans = oo;
	for (int i : stx) {
		if (i > j) break;
		ans = calx(i, x);
	}
	return ans;
}

void oprx(int l, int r) {
	stx.clear(); vc.clear();
	for (int i = l; i < r; i++) {
		int v = ind[i];
		vc.pb(v); lsx[i - l].clear();
	}
	reverse(all(vc));
	for (int fx = len(vc) - 1; fx >= 0; fx--) {
		int i = vc[fx]; addx(i);
		while (len(lsx[fx]) >= 1) {
			int j = lsx[fx].back(); lsx[fx].pop_back();
			delx(j, i);
		}
		for (auto f : Q[i]) {
			int j = f.F, x = f.S.F, w = f.S.S;
			ans[w] = min(ans[w], val1[w] + getx(j, x));
		}
	}
}

void solvex(int T) {
	for (int i = 0; i <= n; i++) {
		adj[i].clear(); Q[i].clear();
	}
	for (int i = n - 1; i >= 0; i--) {
		for (R[i] = i + 1; R[i] != n && A[i] > A[R[i]]; R[i] = R[R[i]]);
	}
	for (int i = n - 1; i >= 0; i--) {
		adj[R[i]].pb(i);
		if (R[i] == n) {
			valx[i] = A[i].F; valr[i] = A[i].F;
			vals[i] = valr[i]; valf[i] = valx[i];
		}
		else {
			ll Rx = (T == 0) ? dp[GI(i, R[i])] : dp[GI(n - R[i] - 1, n - i - 1)];
			valx[i] = A[i].F + Rx;
			valr[i] = A[i].F * (R[i] - i);
			vals[i] = valr[i] + vals[R[i]];
			valf[i] = valx[i] + vals[R[i]];
		}
		valf[i] += A[i].F * i;
	}
	pre_dfs(n); timer = 0; res_dfs(n);
	for (int i = 0; i < q; i++) {
		int l = Q1[i].F, r = Q1[i].S;
		cal_val(l, r, l, i);
		val1[i] -= vals[r];
	}
	int j = 1;
	for (int i = 2; i <= n; i++) {
		int v = ind[i - 1], u = ind[i];
		if (v != par[u]) {
			oprx(j, i);
			j = i;
		}
	}
	oprx(j, n + 1);
}

vector<ll> minimum_costs(vector<int> Hx, vector<int> Lx, vector<int> Rx) {
	n = len(Hx); q = len(Lx);
	for (int i = 0; i < n; i++) A[i] = Mp(Hx[i], i);
	build_rmq();
	for (int i = 0; i < n; i++) {
		for (L[i] = i - 1; L[i] != -1 && A[i] > A[L[i]]; L[i] = L[L[i]]);
		if (L[i] != -1) ls.pb(Mp(i - L[i], Mp(L[i], i)));
	}
	for (int i = n - 1; i >= 0; i--) {
		for (R[i] = i + 1; R[i] != n && A[i] > A[R[i]]; R[i] = R[R[i]]);
		if (R[i] != n) ls.pb(Mp(R[i] - i, Mp(i, R[i])));
	}
	sort(all(ls)); ls.resize(unique(all(ls)) - ls.begin());
	for (int i = 0; i < len(ls); i++) {
		int l = ls[i].S.F, r = ls[i].S.S;
		if (r - l <= 1) dp[i] = 0;
		else {
			int j = get_max(l + 1, r).S;
			dp[i] = min(dp[GI(l, j)] + A[j].F * (r - j), dp[GI(j, r)] + A[j].F * (j - l));
		}
	}
	for (int i = 0; i < q; i++) {
		Qx[i] = Mp(Lx[i], Rx[i] + 1);
		int l = Qx[i].F, r = Qx[i].S;
		int j = get_max(l, r).S; ans.pb(A[j].F * (r - l));
		Q1[i] = Mp(l, j); val1[i] = A[j].F * (r - j);
		Q2[i] = Mp(n - r, n - j - 1); val2[i] = A[j].F * (j - l + 1);
	}
	for (int T = 0; T < 2; T++) {
		solvex(T);
		reverse(A, A + n);
		for (int i = 0; i < q; i++) {
			swap(Q1[i], Q2[i]);
			swap(val1[i], val2[i]);
		}
	}
	return ans;
}

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