Submission #432965

#	Time	Username	Problem	Language	Result	Execution time	Memory
432965		frodakcin	Meetings (IOI18_meetings)	C++11	60 / 100	5590 ms	144696 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40