oj.uz

답안 #116312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116312 2019-06-12T07:48:51 Z roseanne_pcy 모임들 (IOI18_meetings) C++14
100 / 100
 5378 ms 334160 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

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 67892 KB Output is correct
2 Correct 69 ms 68060 KB Output is correct
3 Correct 70 ms 68056 KB Output is correct
4 Correct 69 ms 67960 KB Output is correct
5 Correct 69 ms 68060 KB Output is correct
6 Correct 68 ms 68444 KB Output is correct
7 Correct 69 ms 67992 KB Output is correct
8 Correct 67 ms 68572 KB Output is correct
9 Correct 68 ms 68316 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 67892 KB Output is correct
2 Correct 69 ms 68060 KB Output is correct
3 Correct 70 ms 68056 KB Output is correct
4 Correct 69 ms 67960 KB Output is correct
5 Correct 69 ms 68060 KB Output is correct
6 Correct 68 ms 68444 KB Output is correct
7 Correct 69 ms 67992 KB Output is correct
8 Correct 67 ms 68572 KB Output is correct
9 Correct 68 ms 68316 KB Output is correct
10 Correct 78 ms 68572 KB Output is correct
11 Correct 76 ms 68572 KB Output is correct
12 Correct 79 ms 68604 KB Output is correct
13 Correct 78 ms 68540 KB Output is correct
14 Correct 81 ms 69284 KB Output is correct
15 Correct 76 ms 68572 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 67804 KB Output is correct
2 Correct 141 ms 72512 KB Output is correct
3 Correct 471 ms 93572 KB Output is correct
4 Correct 405 ms 80936 KB Output is correct
5 Correct 338 ms 89468 KB Output is correct
6 Correct 386 ms 94320 KB Output is correct
7 Correct 429 ms 99416 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 67804 KB Output is correct
2 Correct 141 ms 72512 KB Output is correct
3 Correct 471 ms 93572 KB Output is correct
4 Correct 405 ms 80936 KB Output is correct
5 Correct 338 ms 89468 KB Output is correct
6 Correct 386 ms 94320 KB Output is correct
7 Correct 429 ms 99416 KB Output is correct
8 Correct 508 ms 82556 KB Output is correct
9 Correct 412 ms 82092 KB Output is correct
10 Correct 485 ms 82576 KB Output is correct
11 Correct 465 ms 79452 KB Output is correct
12 Correct 392 ms 78964 KB Output is correct
13 Correct 455 ms 79612 KB Output is correct
14 Correct 509 ms 95748 KB Output is correct
15 Correct 378 ms 79468 KB Output is correct
16 Correct 439 ms 95604 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 67892 KB Output is correct
2 Correct 69 ms 68060 KB Output is correct
3 Correct 70 ms 68056 KB Output is correct
4 Correct 69 ms 67960 KB Output is correct
5 Correct 69 ms 68060 KB Output is correct
6 Correct 68 ms 68444 KB Output is correct
7 Correct 69 ms 67992 KB Output is correct
8 Correct 67 ms 68572 KB Output is correct
9 Correct 68 ms 68316 KB Output is correct
10 Correct 78 ms 68572 KB Output is correct
11 Correct 76 ms 68572 KB Output is correct
12 Correct 79 ms 68604 KB Output is correct
13 Correct 78 ms 68540 KB Output is correct
14 Correct 81 ms 69284 KB Output is correct
15 Correct 76 ms 68572 KB Output is correct
16 Correct 63 ms 67804 KB Output is correct
17 Correct 141 ms 72512 KB Output is correct
18 Correct 471 ms 93572 KB Output is correct
19 Correct 405 ms 80936 KB Output is correct
20 Correct 338 ms 89468 KB Output is correct
21 Correct 386 ms 94320 KB Output is correct
22 Correct 429 ms 99416 KB Output is correct
23 Correct 508 ms 82556 KB Output is correct
24 Correct 412 ms 82092 KB Output is correct
25 Correct 485 ms 82576 KB Output is correct
26 Correct 465 ms 79452 KB Output is correct
27 Correct 392 ms 78964 KB Output is correct
28 Correct 455 ms 79612 KB Output is correct
29 Correct 509 ms 95748 KB Output is correct
30 Correct 378 ms 79468 KB Output is correct
31 Correct 439 ms 95604 KB Output is correct
32 Correct 3359 ms 154716 KB Output is correct
33 Correct 2809 ms 152988 KB Output is correct
34 Correct 3554 ms 156112 KB Output is correct
35 Correct 3777 ms 158208 KB Output is correct
36 Correct 2953 ms 153732 KB Output is correct
37 Correct 3767 ms 156436 KB Output is correct
38 Correct 4893 ms 280576 KB Output is correct
39 Correct 5378 ms 280580 KB Output is correct
40 Correct 4651 ms 216184 KB Output is correct
41 Correct 3805 ms 331384 KB Output is correct
42 Correct 4471 ms 334160 KB Output is correct
43 Correct 4517 ms 334132 KB Output is correct
44 Correct 4958 ms 252452 KB Output is correct