oj.uz

Submission #143937

# Submission time Handle Problem Language Result Execution time Memory
143937 2019-08-15T13:17:17 Z WhipppedCream Meetings (IOI18_meetings) C++17
100 / 100
 5388 ms 352780 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67832 KB Output is correct
2 Correct 68 ms 68104 KB Output is correct
3 Correct 69 ms 68104 KB Output is correct
4 Correct 69 ms 68020 KB Output is correct
5 Correct 67 ms 68100 KB Output is correct
6 Correct 69 ms 68540 KB Output is correct
7 Correct 68 ms 68060 KB Output is correct
8 Correct 69 ms 68668 KB Output is correct
9 Correct 67 ms 68316 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67832 KB Output is correct
2 Correct 68 ms 68104 KB Output is correct
3 Correct 69 ms 68104 KB Output is correct
4 Correct 69 ms 68020 KB Output is correct
5 Correct 67 ms 68100 KB Output is correct
6 Correct 69 ms 68540 KB Output is correct
7 Correct 68 ms 68060 KB Output is correct
8 Correct 69 ms 68668 KB Output is correct
9 Correct 67 ms 68316 KB Output is correct
10 Correct 78 ms 68648 KB Output is correct
11 Correct 76 ms 68684 KB Output is correct
12 Correct 90 ms 68600 KB Output is correct
13 Correct 86 ms 68668 KB Output is correct
14 Correct 80 ms 69492 KB Output is correct
15 Correct 75 ms 68688 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 67872 KB Output is correct
2 Correct 140 ms 73108 KB Output is correct
3 Correct 467 ms 95604 KB Output is correct
4 Correct 399 ms 82916 KB Output is correct
5 Correct 345 ms 91456 KB Output is correct
6 Correct 367 ms 96336 KB Output is correct
7 Correct 415 ms 101476 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 67872 KB Output is correct
2 Correct 140 ms 73108 KB Output is correct
3 Correct 467 ms 95604 KB Output is correct
4 Correct 399 ms 82916 KB Output is correct
5 Correct 345 ms 91456 KB Output is correct
6 Correct 367 ms 96336 KB Output is correct
7 Correct 415 ms 101476 KB Output is correct
8 Correct 492 ms 84636 KB Output is correct
9 Correct 411 ms 84156 KB Output is correct
10 Correct 478 ms 84696 KB Output is correct
11 Correct 456 ms 81428 KB Output is correct
12 Correct 391 ms 80944 KB Output is correct
13 Correct 454 ms 81620 KB Output is correct
14 Correct 514 ms 97840 KB Output is correct
15 Correct 406 ms 81468 KB Output is correct
16 Correct 448 ms 97580 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67832 KB Output is correct
2 Correct 68 ms 68104 KB Output is correct
3 Correct 69 ms 68104 KB Output is correct
4 Correct 69 ms 68020 KB Output is correct
5 Correct 67 ms 68100 KB Output is correct
6 Correct 69 ms 68540 KB Output is correct
7 Correct 68 ms 68060 KB Output is correct
8 Correct 69 ms 68668 KB Output is correct
9 Correct 67 ms 68316 KB Output is correct
10 Correct 78 ms 68648 KB Output is correct
11 Correct 76 ms 68684 KB Output is correct
12 Correct 90 ms 68600 KB Output is correct
13 Correct 86 ms 68668 KB Output is correct
14 Correct 80 ms 69492 KB Output is correct
15 Correct 75 ms 68688 KB Output is correct
16 Correct 62 ms 67872 KB Output is correct
17 Correct 140 ms 73108 KB Output is correct
18 Correct 467 ms 95604 KB Output is correct
19 Correct 399 ms 82916 KB Output is correct
20 Correct 345 ms 91456 KB Output is correct
21 Correct 367 ms 96336 KB Output is correct
22 Correct 415 ms 101476 KB Output is correct
23 Correct 492 ms 84636 KB Output is correct
24 Correct 411 ms 84156 KB Output is correct
25 Correct 478 ms 84696 KB Output is correct
26 Correct 456 ms 81428 KB Output is correct
27 Correct 391 ms 80944 KB Output is correct
28 Correct 454 ms 81620 KB Output is correct
29 Correct 514 ms 97840 KB Output is correct
30 Correct 406 ms 81468 KB Output is correct
31 Correct 448 ms 97580 KB Output is correct
32 Correct 3423 ms 173220 KB Output is correct
33 Correct 2810 ms 171592 KB Output is correct
34 Correct 3609 ms 174424 KB Output is correct
35 Correct 3855 ms 176684 KB Output is correct
36 Correct 2964 ms 172304 KB Output is correct
37 Correct 3738 ms 175028 KB Output is correct
38 Correct 4865 ms 299340 KB Output is correct
39 Correct 5388 ms 299316 KB Output is correct
40 Correct 4649 ms 234876 KB Output is correct
41 Correct 3861 ms 349528 KB Output is correct
42 Correct 4543 ms 352780 KB Output is correct
43 Correct 4635 ms 352696 KB Output is correct
44 Correct 4883 ms 270940 KB Output is correct