oj.uz

Submission #432965

# Submission time Handle Problem Language Result Execution time Memory
432965 2021-06-18T16:05:31 Z frodakcin Meetings (IOI18_meetings) C++11
60 / 100
 5500 ms 144696 KB 
#include "meetings.h"
#include <cstring>
#include <cstdio>
#include <stack>
#include <algorithm>

template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}

using ll = long long;

const ll INF = 0x3f3f3f3f3f3f3f3f;

std::vector<int> H;
int N;

ll brute(int L, int R)
{
	std::vector<ll> bl, br;
	bl.reserve(R-L), br.reserve(R-L);
	int len = R-L;
	{
		std::stack<int> s; s.push(L-1);
		ll cur=0;
		for(int i=L;i<R;++i)
		{
			cur += H[i];
			for(;s.size()>1 && H[i] > H[s.top()];)
			{
				int pr=s.top();
				s.pop();
				cur += (ll)(pr-s.top())*(H[i]-H[pr]);
			}
			bl.push_back(cur);
			s.push(i);
		}
	}

	{
		std::stack<int> s; s.push(R);
		ll cur=0;
		for(int i=R-1;i>=L;--i)
		{
			cur += H[i];
			for(;s.size()>1 && H[i] > H[s.top()];)
			{
				int pr=s.top();
				s.pop();
				cur += (ll)(s.top()-pr)*(H[i]-H[pr]);
			}
			br.push_back(cur);
			s.push(i);
		}
	}

	ll ans=INF;
	for(int i=0;i<len;++i)
		ckmin(ans, bl[i]+br[len-1-i]-H[L+i]);
	return ans;
}

const int MH = 20;
struct stval
{
	public:
		int vl[MH], vr[MH], ul[MH], ur[MH]; //v = I have the target, u = you have the target
		int max;
		stval()
		{
			memset(vl, 0, sizeof vl);
			memset(vr, 0, sizeof vr);
			memset(ul, 0, sizeof ul);
			memset(ur, 0, sizeof ur);
			max=0;
		}
		stval(int _n)
		{
			if(_n==-1)
			{
				memset(vl, 0x3f, sizeof vl);
				memset(vr, 0x3f, sizeof vr);
				memset(ul, 0x3f, sizeof ul);
				memset(ur, 0x3f, sizeof ur);
				max=0;
			}
			else
			{
				max = _n;
				for(int i=0;i<=max;++i)
					vl[i]=vr[i]=max;
				for(int i=0;i<MH;++i)
					ul[i]=ur[i]=std::max(max, i);
			}
		}
		/*
		stval& operator += (const stval& o)
		{
			for(int i=0;i<max;++i)
				vl[i] += o.ul[max];
			for(int i=max;i<o.max;++i)
				vl[i] = ur[i]+o.vl[i];

			for(int i=0;i<o.max;++i)
				vr[i] = o.vr[i]+ur[o.max];
			for(int i=o.max;i<max;++i)
				vr[i] += o.ul[max];

			for(int i=0;i<MH;++i)
				ul[i] += o.ul[std::max(max, i)];
			for(int i=0;i<MH;++i)
				ur[i] = o.ur[i] + ur[std::max(o.max, i)];

			ckmax(max, o.max);
			return *this;
		}
		*/
		friend stval operator + (const stval& a, const stval& b)
		{
			stval f(-1);
			f.max = std::max(a.max, b.max);

			for(int i=0;i<=a.max;++i)
				ckmin(f.vl[i], a.vl[i] + b.ul[a.max]);
			for(int i=0;i<=a.max;++i)
				ckmin(f.vl[a.max], a.vr[i] + b.ul[i]);
			for(int i=0;i<=b.max;++i)
				ckmin(f.vl[std::max(a.max, i)], a.ur[i] + b.vl[i]);
			if(b.max >= a.max)
				for(int i=0;i<=b.max;++i)
					ckmin(f.vl[b.max], a.ur[b.max] + b.vr[i]);

			for(int i=0;i<=b.max;++i)
				ckmin(f.vr[i], b.vr[i] + a.ur[b.max]);
			for(int i=0;i<=b.max;++i)
				ckmin(f.vr[b.max], b.vl[i] + a.ur[i]);
			for(int i=0;i<=a.max;++i)
				ckmin(f.vr[std::max(b.max, i)], b.ul[i] + a.vr[i]);
			if(a.max >= b.max)
				for(int i=0;i<=a.max;++i)
					ckmin(f.vr[a.max], a.vl[i] + b.ul[a.max]);

			for(int i=0;i<MH;++i)
				f.ul[i] = a.ul[i] + b.ul[std::max(i, a.max)];
			for(int i=0;i<MH;++i)
				f.ur[i] = b.ur[i] + a.ur[std::max(i, b.max)];

			return f;
		}
};

stval st[1 << 18];
void build(int n, int l, int r)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		build(n<<1, l, m);
		build(n<<1|1, m, r);
		st[n]=st[n<<1]+st[n<<1|1];
	}
	else
		st[n]=stval(H[l]);
}

stval qv;
void qry(int n, int l, int r, int ql, int qr)
{
	if(ql <= l&&r <= qr)
	{
		//printf("%d\n", qv.vr[2]);
		//printf(" + %d\n", st[n].ul[2]);
		qv = qv + st[n];
		//printf(" = %d (%d)\n", qv.vr[8], st[n].max);
	}
	else
	{
		int m=l+(r-l)/2;
		if(ql < m) qry(n<<1, l, m, ql, qr);
		if(m < qr) qry(n<<1|1, m, r, ql, qr);
	}
}

std::vector<long long> minimum_costs(std::vector<int> _H, std::vector<int> L,
                                     std::vector<int> R) {
	H = _H;
	N = H.size();
	int maxh = *std::max_element(H.begin(), H.end());
	if(maxh <= 20)
	{
		for(int& x:H) --x;
		build(1, 0, N);
	}

  int Q = L.size();
  std::vector<ll> C(Q);
  for (int j = 0; j < Q; ++j)
	{
		if(maxh <= 20)
		{
			qv = stval();
			qry(1, 0, N, L[j], R[j]+1);

			C[j]=INF;
			for(int i=0;i<=qv.max;++i)
				ckmin(C[j], (ll)std::min(qv.vl[i], qv.vr[i]));
			C[j]+=(R[j]-L[j]+1);
		}
		else
			C[j]=brute(L[j], R[j]+1);
	}
  return C;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83284 KB Output is correct
2 Correct 38 ms 83392 KB Output is correct
3 Correct 39 ms 83440 KB Output is correct
4 Correct 39 ms 83344 KB Output is correct
5 Correct 44 ms 83360 KB Output is correct
6 Correct 39 ms 83476 KB Output is correct
7 Correct 38 ms 83308 KB Output is correct
8 Correct 39 ms 83296 KB Output is correct
9 Correct 39 ms 83404 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83284 KB Output is correct
2 Correct 38 ms 83392 KB Output is correct
3 Correct 39 ms 83440 KB Output is correct
4 Correct 39 ms 83344 KB Output is correct
5 Correct 44 ms 83360 KB Output is correct
6 Correct 39 ms 83476 KB Output is correct
7 Correct 38 ms 83308 KB Output is correct
8 Correct 39 ms 83296 KB Output is correct
9 Correct 39 ms 83404 KB Output is correct
10 Correct 378 ms 83764 KB Output is correct
11 Correct 1020 ms 83660 KB Output is correct
12 Correct 355 ms 83728 KB Output is correct
13 Correct 1024 ms 83656 KB Output is correct
14 Correct 217 ms 83676 KB Output is correct
15 Correct 293 ms 83664 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 83244 KB Output is correct
2 Correct 153 ms 84756 KB Output is correct
3 Correct 436 ms 86920 KB Output is correct
4 Correct 437 ms 86924 KB Output is correct
5 Correct 165 ms 86980 KB Output is correct
6 Correct 355 ms 86860 KB Output is correct
7 Correct 455 ms 86900 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 83244 KB Output is correct
2 Correct 153 ms 84756 KB Output is correct
3 Correct 436 ms 86920 KB Output is correct
4 Correct 437 ms 86924 KB Output is correct
5 Correct 165 ms 86980 KB Output is correct
6 Correct 355 ms 86860 KB Output is correct
7 Correct 455 ms 86900 KB Output is correct
8 Correct 780 ms 86912 KB Output is correct
9 Correct 920 ms 88920 KB Output is correct
10 Correct 582 ms 88928 KB Output is correct
11 Correct 783 ms 88924 KB Output is correct
12 Correct 963 ms 88812 KB Output is correct
13 Correct 593 ms 88952 KB Output is correct
14 Correct 759 ms 89016 KB Output is correct
15 Correct 645 ms 88928 KB Output is correct
16 Correct 651 ms 88984 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 83284 KB Output is correct
2 Correct 38 ms 83392 KB Output is correct
3 Correct 39 ms 83440 KB Output is correct
4 Correct 39 ms 83344 KB Output is correct
5 Correct 44 ms 83360 KB Output is correct
6 Correct 39 ms 83476 KB Output is correct
7 Correct 38 ms 83308 KB Output is correct
8 Correct 39 ms 83296 KB Output is correct
9 Correct 39 ms 83404 KB Output is correct
10 Correct 378 ms 83764 KB Output is correct
11 Correct 1020 ms 83660 KB Output is correct
12 Correct 355 ms 83728 KB Output is correct
13 Correct 1024 ms 83656 KB Output is correct
14 Correct 217 ms 83676 KB Output is correct
15 Correct 293 ms 83664 KB Output is correct
16 Correct 37 ms 83244 KB Output is correct
17 Correct 153 ms 84756 KB Output is correct
18 Correct 436 ms 86920 KB Output is correct
19 Correct 437 ms 86924 KB Output is correct
20 Correct 165 ms 86980 KB Output is correct
21 Correct 355 ms 86860 KB Output is correct
22 Correct 455 ms 86900 KB Output is correct
23 Correct 780 ms 86912 KB Output is correct
24 Correct 920 ms 88920 KB Output is correct
25 Correct 582 ms 88928 KB Output is correct
26 Correct 783 ms 88924 KB Output is correct
27 Correct 963 ms 88812 KB Output is correct
28 Correct 593 ms 88952 KB Output is correct
29 Correct 759 ms 89016 KB Output is correct
30 Correct 645 ms 88928 KB Output is correct
31 Correct 651 ms 88984 KB Output is correct
32 Execution timed out 5590 ms 144696 KB Time limit exceeded
33 Halted 0 ms 0 KB -