oj.uz

Submission #132211

# Submission time Handle Problem Language Result Execution time Memory
132211 2019-07-18T13:18:47 Z WannnabeIOI Meetings (IOI18_meetings) C++14
100 / 100
 5493 ms 334460 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 67912 KB Output is correct
2 Correct 67 ms 67960 KB Output is correct
3 Correct 68 ms 68036 KB Output is correct
4 Correct 67 ms 68092 KB Output is correct
5 Correct 68 ms 68084 KB Output is correct
6 Correct 69 ms 68444 KB Output is correct
7 Correct 69 ms 68088 KB Output is correct
8 Correct 68 ms 68616 KB Output is correct
9 Correct 69 ms 68288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67912 KB Output is correct
2 Correct 67 ms 67960 KB Output is correct
3 Correct 68 ms 68036 KB Output is correct
4 Correct 67 ms 68092 KB Output is correct
5 Correct 68 ms 68084 KB Output is correct
6 Correct 69 ms 68444 KB Output is correct
7 Correct 69 ms 68088 KB Output is correct
8 Correct 68 ms 68616 KB Output is correct
9 Correct 69 ms 68288 KB Output is correct
10 Correct 79 ms 68496 KB Output is correct
11 Correct 77 ms 68564 KB Output is correct
12 Correct 80 ms 68568 KB Output is correct
13 Correct 78 ms 68548 KB Output is correct
14 Correct 79 ms 69388 KB Output is correct
15 Correct 76 ms 68580 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 67908 KB Output is correct
2 Correct 141 ms 72520 KB Output is correct
3 Correct 485 ms 93612 KB Output is correct
4 Correct 409 ms 80932 KB Output is correct
5 Correct 336 ms 89412 KB Output is correct
6 Correct 384 ms 94300 KB Output is correct
7 Correct 426 ms 99444 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 67908 KB Output is correct
2 Correct 141 ms 72520 KB Output is correct
3 Correct 485 ms 93612 KB Output is correct
4 Correct 409 ms 80932 KB Output is correct
5 Correct 336 ms 89412 KB Output is correct
6 Correct 384 ms 94300 KB Output is correct
7 Correct 426 ms 99444 KB Output is correct
8 Correct 488 ms 82648 KB Output is correct
9 Correct 411 ms 82700 KB Output is correct
10 Correct 487 ms 83168 KB Output is correct
11 Correct 461 ms 80072 KB Output is correct
12 Correct 389 ms 79576 KB Output is correct
13 Correct 451 ms 80276 KB Output is correct
14 Correct 517 ms 96372 KB Output is correct
15 Correct 390 ms 80156 KB Output is correct
16 Correct 445 ms 96104 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67912 KB Output is correct
2 Correct 67 ms 67960 KB Output is correct
3 Correct 68 ms 68036 KB Output is correct
4 Correct 67 ms 68092 KB Output is correct
5 Correct 68 ms 68084 KB Output is correct
6 Correct 69 ms 68444 KB Output is correct
7 Correct 69 ms 68088 KB Output is correct
8 Correct 68 ms 68616 KB Output is correct
9 Correct 69 ms 68288 KB Output is correct
10 Correct 79 ms 68496 KB Output is correct
11 Correct 77 ms 68564 KB Output is correct
12 Correct 80 ms 68568 KB Output is correct
13 Correct 78 ms 68548 KB Output is correct
14 Correct 79 ms 69388 KB Output is correct
15 Correct 76 ms 68580 KB Output is correct
16 Correct 63 ms 67908 KB Output is correct
17 Correct 141 ms 72520 KB Output is correct
18 Correct 485 ms 93612 KB Output is correct
19 Correct 409 ms 80932 KB Output is correct
20 Correct 336 ms 89412 KB Output is correct
21 Correct 384 ms 94300 KB Output is correct
22 Correct 426 ms 99444 KB Output is correct
23 Correct 488 ms 82648 KB Output is correct
24 Correct 411 ms 82700 KB Output is correct
25 Correct 487 ms 83168 KB Output is correct
26 Correct 461 ms 80072 KB Output is correct
27 Correct 389 ms 79576 KB Output is correct
28 Correct 451 ms 80276 KB Output is correct
29 Correct 517 ms 96372 KB Output is correct
30 Correct 390 ms 80156 KB Output is correct
31 Correct 445 ms 96104 KB Output is correct
32 Correct 3406 ms 155592 KB Output is correct
33 Correct 2790 ms 153868 KB Output is correct
34 Correct 3643 ms 156844 KB Output is correct
35 Correct 3812 ms 158956 KB Output is correct
36 Correct 2938 ms 154456 KB Output is correct
37 Correct 3797 ms 157252 KB Output is correct
38 Correct 4981 ms 281424 KB Output is correct
39 Correct 5493 ms 281396 KB Output is correct
40 Correct 4703 ms 217048 KB Output is correct
41 Correct 3822 ms 332176 KB Output is correct
42 Correct 4545 ms 334460 KB Output is correct
43 Correct 4563 ms 334180 KB Output is correct
44 Correct 4949 ms 252448 KB Output is correct