Submission #120908

#	Time	Username	Problem	Language	Result	Execution time	Memory
120908		sebinkim	Meetings (IOI18_meetings)	C++14	100 / 100	2011 ms	325512 KiB

meetings

#include "meetings.h"

#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

struct minseg{
	pii T[2202020];
	int sz = 1 << 20;
	
	void init(vector <int> &H)
	{
		int i;
		
		for(i=0; i<H.size(); i++){
			T[i + sz] = pii(H[i], i);
		}
		
		for(i=sz-1; i; i--){
			T[i] = max(T[i << 1], T[i << 1 | 1]);
		}
	}
	
	int getmax(int l, int r)
	{
		pii ret(-1, -1);
		
		l += sz; r += sz;
		for(; l<=r; ){
			if(l & 1) ret = max(ret, T[l]);
			if(~r & 1) ret = max(ret, T[r]);
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
		
		return ret.second;
	}
};

struct line{
	ll x, a, b;
	line() {}
	line(ll x, ll a, ll b) : x(x), a(a), b(b) {}
};

struct deq{
	line D[808080];
	int S[808080], E[808080];
	ll V[808080];
	int n;
	bool t;
	
	void init(bool _t, int _n)
	{
		int i;
		
		t = _t; n = _n;
		
		for(i=0; i<n; i++){
			S[i] = i; E[i] = i;
			D[i] = line(i, 0, 0);
		}
	}
	
	void addval(int p, ll v)
	{
		if(t) p = n - 1 - p;
		V[p] += v;
	}
	
	void addline(int p, ll x, ll a, ll b)
	{
		if(t){
			p = n - 1 - p, x = n - 1 - x;
			b = (n - 1) * a + b; a = -a;
		}
		
		int &s = S[p], &e = E[p];
		
		b -= V[p];
		
		for(; s<=e; e--){
			if(D[e].a == a && D[e].b < b) return;
			if(D[e].a * D[e].x + D[e].b < a * D[e].x + b){
				D[++e] = line((D[e].b - b) / (a - D[e].a) + 1, a, b);
				return;
			}
		}
		
		D[++e] = line(x, a, b);
	}
	
	ll getval(int p, ll x)
	{
		if(t) p = n - 1 - p, x = n - 1 - x;
		
		int k = upper_bound(D + S[p], D + E[p] + 1, x, [&](ll x, line l){
			return x < l.x;
		}) - D - 1;
		
		return D[k].a * x + D[k].b + V[p];
	}
	
	void merge(int p, int q)
	{
		if(t) p = n - 1 - p, q = n - 1 - q;
		
		int i;
		
		if(E[p] - S[p] < E[q] - S[q]){
			swap(S[p], S[q]); swap(E[p], E[q]);
			swap(V[p], V[q]);
		}
		
		if(S[p] < S[q]){
			for(i=S[q]; i<=E[q]; i++){
				D[i].b += V[q] - V[p];
				D[++E[p]] = D[i];
			}
		}
		else{
			for(i=E[q]; i>=S[q]; i--){
				D[i].b += V[q] - V[p];
				D[--S[p]] = D[i];
			}
		}
	}
};

minseg T;
deq DL, DR;
vector <int> H, L, R;
vector <int> Q[808080];
vector <ll> A;
int n;

int dnc(int s, int e)
{
	if(s > e) return -1;
	
	int m, l, r;
	ll v, h;
	
	m = T.getmax(s, e);	h = H[m];
	l = dnc(s, m - 1); r = dnc(m + 1, e);
	
	for(int &q: Q[m]){
		if(L[q] == m && R[q] == m) A[q] = h;
		else if(L[q] == m) A[q] = DR.getval(r, R[q]) + h;
		else if(R[q] == m) A[q] = DL.getval(l, L[q]) + h;
		else A[q] = min(DL.getval(l, L[q]) + h * (R[q] - m + 1),
						DR.getval(r, R[q]) + h * (m - L[q] + 1));
	}
	
	if(l != -1) DL.merge(m, l);
	DL.addval(m, h * (e - m + 1));
	DL.addline(m, s, -h, (r != -1? DL.getval(r, m + 1) : 0) + h * (m + 1));
	if(r != -1) DL.merge(m, r);
	
	if(r != -1) DR.merge(m, r);
	DR.addval(m, h * (m - s + 1));
	DR.addline(m, e, h, (l != -1? DR.getval(l, m - 1) : 0) - h * (m - 1));
	if(l != -1) DR.merge(m, l);
	
	return m;
}

vector <ll> minimum_costs(vector <int> _H, vector <int> _L, vector <int> _R)
{
	int i;
	
	swap(H, _H); swap(L, _L); swap(R, _R);
	n = H.size(); A.resize(L.size());
	
	T.init(H); DL.init(0, n); DR.init(1, n);
	
	for(i=0; i<L.size(); i++){
		Q[T.getmax(L[i], R[i])].push_back(i);
	}
	
	dnc(0, n - 1);
	
	return A;
}

Compilation message (stderr)

meetings.cpp: In member function 'void minseg::init(std::vector<int>&)':
meetings.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<H.size(); i++){
            ~^~~~~~~~~
meetings.cpp: In member function 'int minseg::getmax(int, int)':
meetings.cpp:36:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
meetings.cpp:37:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
meetings.cpp: In member function 'void deq::addline(int, ll, ll, ll)':
meetings.cpp:89:7: warning: operation on 'e' may be undefined [-Wsequence-point]
     D[++e] = line((D[e].b - b) / (a - D[e].a) + 1, a, b);
       ^~~
meetings.cpp:89:7: warning: operation on 'e' may be undefined [-Wsequence-point]
meetings.cpp: In function 'int dnc(int, int)':
meetings.cpp:146:5: warning: unused variable 'v' [-Wunused-variable]
  ll v, h;
     ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:181:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<L.size(); i++){
           ~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40