Submission #143937

#	Time	Username	Problem	Language	Result	Execution time	Memory
143937		WhipppedCream	Meetings (IOI18_meetings)	C++17	100 / 100	5388 ms	352780 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 750005;

int n, q;

struct rng
{
	int ed;
	ll m, b;
	rng(int _ed = 0, ll _m = 0, ll _b = 0) : ed(_ed), m(_m), b(_b){}
	ll eval(int x) 
	{
		return m*x+b;
	}
};

map<int, rng> png;

int arr[maxn];
int st[4*maxn];

void build(int p = 1, int L = 0, int R = n-1)
{
	if(L == R)
	{
		st[p] = L;
		return;
	}
	int M = (L+R)/2;
	build(2*p, L, M);
	build(2*p+1, M+1, R);
	if(arr[st[2*p]]>= arr[st[2*p+1]]) st[p] = st[2*p];
	else st[p] = st[2*p+1]; 
}

int rmq(int i, int j, int p = 1, int L = 0, int R = n-1)
{
	if(i> R || j< L) return -1;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	int x = rmq(i, j, 2*p, L, M);
	int y = rmq(i, j, 2*p+1, M+1, R);
	if(x == -1) return y;
	if(y == -1) return x;
	return (arr[x]>= arr[y])?x:y;
}

void build2(int p = 1, int L = 0, int R = n-1)
{
	if(L == R)
	{
		st[p] = L;
		return;
	}
	int M = (L+R)/2;
	build2(2*p, L, M);
	build2(2*p+1, M+1, R);
	if(arr[st[2*p]]> arr[st[2*p+1]]) st[p] = st[2*p];
	else st[p] = st[2*p+1]; 
}

int rmq2(int i, int j, int p = 1, int L = 0, int R = n-1)
{
	if(i> R || j< L) return -1;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	int x = rmq2(i, j, 2*p, L, M);
	int y = rmq2(i, j, 2*p+1, M+1, R);
	if(x == -1) return y;
	if(y == -1) return x;
	return (arr[x]> arr[y])?x:y;
}

vector<int> tree[maxn];

vector<ii> ql[maxn];
vector<ii> qr[maxn];
ll ansl[maxn];
ll ansr[maxn];

int cartesian(int L, int R)
{
	if(L> R) return -1;
	int u = rmq(L, R);
	int x = cartesian(L, u-1);
	int y = cartesian(u+1, R);
	if(x != -1) tree[u].pb(x);
	if(y != -1) tree[u].pb(y);
	return u;
}

int cartesian2(int L, int R)
{
	if(L> R) return -1;
	int u = rmq2(L, R);
	int x = cartesian2(L, u-1);
	int y = cartesian2(u+1, R);
	if(x != -1) tree[u].pb(x);
	if(y != -1) tree[u].pb(y);
	return u;
}

pair<int, int> cov[maxn];
ll lz[maxn];
int sz[maxn];
int arx[maxn];

void solve(int u, vector<ii> *quest, ll *answ)
{
	int lc = -1, rc = -1;
	if(tree[u].size() == 2)
	{
		lc = tree[u][0];
		rc = tree[u][1];
	}
	else if(tree[u].size() == 1)
	{
		if(tree[u][0]< u) lc = tree[u][0];
		else rc = tree[u][0];
	}
	cov[u] = {u, u};
	if(lc != -1) 
	{
		solve(lc, quest, answ);
		cov[u].X = min(cov[u].X, cov[lc].X);
	}
	if(rc != -1)
	{
		solve(rc, quest, answ);
		cov[u].Y = max(cov[u].Y, cov[rc].Y);
	}
	rng here;
	ll midcost;
	if(lc == -1)
	{
		midcost = arr[u];
	}
	else
	{
		auto it = png.upper_bound(u);
		--it;
		midcost = arr[u]+(it->second).eval(u-1)+lz[lc];
	}
	here = rng(u, 0, midcost);
	png[u] = here; 
	// printf("midcost[%d] = %lld\n", u, midcost);
	// printf("solving %d\n", u);
	if(rc != -1)
	{
		ll add = 1LL*(u-cov[u].X+1)*arr[u];
		lz[rc] += add;
		int st = u+1;
		bool fixed = false;
		while(st<= cov[u].Y)
		{
			// printf("%d\n", st);
			rng f2 = png[st];
			int ed = f2.ed;
			rng f1 = rng(0, arr[u], midcost-1LL*arr[u]*u);
			if(f1.eval(ed)<= f2.eval(ed)+lz[rc])
			{
				// printf("this case\n");
				png.erase(st);
				st = ed+1;
				sz[rc]--;
			}
			else
			{
				// printf("bad at %d\n", st);
				int lo = st, hi = ed;
				while(lo< hi)
				{
					int mid = (lo+hi)/2;
					// printf("%d\n", mid);
					if(f1.eval(mid)<= f2.eval(mid)+lz[rc]) lo = mid+1;
					else hi = mid;
				}
				// printf("first to okay: %d\n", lo);
				png.erase(st);
				sz[rc]--;
				if(u+1<= lo-1)
				{
					png[u+1] = rng(lo-1, arr[u], midcost-1LL*arr[u]*u-lz[rc]);
					// printf("{%d, %d} left fuction\n", u+1, lo-1);
					sz[rc]++;
				}
				// else printf("WTF\n");
				png[lo] = f2;
				sz[rc]++;
				fixed = true;
				break;
			}
		}
		// printf("fixed = %d\n", fixed);
		if(!fixed)
		{
			// printf("{%d, %d} left function\n", u+1, cov[u].Y);
			png[u+1] = rng(cov[u].Y, arr[u], midcost-1LL*arr[u]*u-lz[rc]);
			sz[rc]++;
		}
	}
	if(lc != -1 && rc != -1)
	{
		if(sz[lc]< sz[rc])
		{
			int st = cov[u].X;
			while(st< u)
			{
				png[st].b += lz[lc]-lz[rc];
				st = png[st].ed+1;
			}
			png[u].b -= lz[rc];
			lz[u] = lz[rc];
		}
		else
		{
			int st = u+1;
			while(st<= cov[u].Y)
			{
				png[st].b += lz[rc]-lz[lc];
				st = png[st].ed+1;
			}
			png[u].b -= lz[lc];
			lz[u] = lz[lc];
		}
	}
	else if(lc != -1)
	{
		png[u].b -= lz[lc];
		lz[u] = lz[lc];
	}
	else
	{
		png[u].b -= lz[rc];
		lz[u] = lz[rc];
	}
	sz[u] = 1;
	if(lc != -1) sz[u] += sz[lc];
	if(rc != -1) sz[u] += sz[rc];
	for(auto kk : quest[u])
	{
		int want = kk.X, id = kk.Y;
		auto it = png.upper_bound(want);
		--it;
		answ[id] = (it->second).eval(want)+lz[u];
	}
	// printf("rangeL(%d) = %d\n", u, cov[u].X);
	// for(int i = cov[u].X; i<= cov[u].Y; i++)
	// {
	// 	auto it = png.upper_bound(i);
	// 	--it;
	// 	// printf("using %d\n", it->first);
	// 	printf("cost[rangeL(%d), %d] = %lld\n", u, i, (it->second).eval(i)+lz[u]);
	// }
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	n = H.size(); q = L.size();

	for(int i = 0; i< n; i++) arr[i] = H[i];
	build();
	int root = cartesian(0, n-1);
	for(int i = 0; i< q; i++)
	{
		int arg = rmq(L[i], R[i]);
		arx[i] = arg;
		if(arg+1<= R[i])
		{
			int argr = rmq(arg+1, R[i]);
			qr[argr].pb(ii(R[i], i));
		}
		if(L[i]<= arg-1)
		{
			int argl = rmq(L[i], arg-1);
			ql[n-argl-1].pb(ii(n-L[i]-1, i));
			// printf("ql[%d] pb %d\n", n-argl-1, n-L[i]-1);
		}
	}
	// printf("finished\n");
	solve(root, qr, ansr);

	memset(lz, 0, sizeof lz);
	memset(cov, 0, sizeof cov);
	memset(sz, 0, sizeof sz);
	for(int i = 0; i< n; i++) tree[i].clear();
	png.clear();

	for(int i = 0; i< n; i++) arr[i] = H[n-i-1];
	build2();
	root = cartesian2(0, n-1);
	solve(root, ql, ansl);
	
	for(int i = 0; i< n; i++) arr[i] = H[i];
	vector<ll> ret(q);
	for(int i = 0; i< q; i++)
	{
		// printf("ansl[%d] = %lld, ansr[%d] = %lld\n", i, ansl[i], i, ansr[i]);
		ret[i] = min(ansl[i]+1LL*(R[i]-arx[i]+1)*arr[arx[i]], ansr[i]+1LL*(arx[i]-L[i]+1)*arr[arx[i]]);
	}
	return ret;
}

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