Submission #91444

#	Time	Username	Problem	Language	Result	Execution time	Memory
91444		tincamatei	Meetings (IOI18_meetings)	C++14	17 / 100	495 ms	249620 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

const int MAX_N = 750000;
const int MAX_L = 19;

vector<int> h;

int rmq[MAX_L][MAX_N];
int rmqlg[1+MAX_N];

int argmax(int a, int b) {
	if(h[a] >= h[b])
		return a;
	return b;
}

int queryRmq(int a, int b) {
	int s = b - a + 1;
	int l = rmqlg[s];

	return argmax(rmq[l][a], rmq[l][b - (1 << l) + 1]);
}

struct Query {
	int l, r, i;
};

vector<long long> rez;

vector<Query> queries[MAX_N];

struct Range {
	int l, r;
	long long yinter, slope;
};

struct Cell {
	long long lazy;
	deque<Range> ranges;

	long long getDp(int i) {
		if(ranges.size() == 0) return 0LL;
		int st = 0, dr = ranges.size();
		while(dr - st > 1) {
			int mid = (st + dr) / 2;
			if(ranges[mid].l <= i)
				st = mid;
			else
				dr = mid;
		}

		return lazy + ranges[st].yinter + ranges[st].slope * (i - ranges[st].l);
	}
};

void heavyMerge(Cell &st, Cell &dr, Cell &dest) {
	if(st.ranges.size() < dr.ranges.size()) {
		dest.ranges.swap(dr.ranges);
		dest.lazy = dr.lazy;

		for(int i = st.ranges.size() - 1; i >= 0; --i) {
			dest.ranges.push_front(st.ranges[i]);
			dest.ranges.front().yinter += st.lazy - dest.lazy;
		}
	} else {
		dest.ranges.swap(st.ranges);
		dest.lazy = st.lazy;

		for(int i = 0; i < dr.ranges.size(); ++i) {
			dest.ranges.push_back(dr.ranges[i]);
			dest.ranges.back().yinter += dr.lazy - dest.lazy;
		}
	}
}

int intersect(long long a1, long long b1, long long c1, 
              long long a2, long long b2, long long c2) {
	return (b2 - a2 * c2 - b1 + c1 * a1) / (a1 - a2);
}

int intersect2(long long a1, long long b1, long long c1, 
               long long a2, long long b2, long long c2) {
	return (b1 + a1 * c1 - b2 + a2 * c2 + a1 + a2 - 1) / (a1 + a2);
}

void prefCompress(Cell &pref, int root, long long yinter, long long slope, long long cst) {
	int splitr = root;

	//printf("Preffix compression: %d %lld %lld %lld\n", root, yinter, slope, cst);
	
	//for(auto it: pref.ranges)
	//	printf("r: %d %d; %lld+%lldx\n", it.l, it.r, it.yinter + pref.lazy, it.slope);

	// Elimin toate bucatile complete
	while(!pref.ranges.empty() && yinter + slope * (pref.ranges.front().r - root) <= 
	                              pref.getDp(pref.ranges.front().r) + cst) {
		splitr = pref.ranges.front().r;
		pref.ranges.pop_front();
	}
	
	// Vad unde splituiesc ultima bucata
	if(!pref.ranges.empty() && yinter + slope * (pref.ranges.front().l - root) <= 
	                           pref.getDp(pref.ranges.front().l) + cst) {
		Range prt = pref.ranges.front();
		splitr = intersect(slope, yinter, root, 
		                   prt.slope, prt.yinter + pref.lazy + cst, prt.l);
		
		pref.ranges.front().yinter = pref.getDp(splitr + 1) - pref.lazy;
		pref.ranges.front().l = splitr + 1;
	}

	pref.lazy += cst;
	if(root + 1 <= splitr) pref.ranges.push_front({root + 1, splitr, yinter + slope - pref.lazy, slope});
}

void suffCompress(Cell &suff, int root, long long yinter, long long slope, long long cst) {
	int splitl = root;
	// Elimin toate bucatile complete
	while(!suff.ranges.empty() && yinter + slope * (root - suff.ranges.back().l) <= 
	                              suff.getDp(suff.ranges.back().l) + cst) {
		splitl = suff.ranges.back().l;
		suff.ranges.pop_back();
	}
	// Vad unde splituiesc ultima bucata
	if(!suff.ranges.empty() && yinter + slope * (root - suff.ranges.front().l) <= 
	                           suff.getDp(suff.ranges.front().r) + cst) {
		Range prt = suff.ranges.front();
		splitl = intersect2(slope, yinter, root, 
		                   prt.slope, prt.yinter + cst, prt.l);

		suff.ranges.back().r = splitl - 1;
	}

	suff.lazy += cst;
	if(splitl <= root - 1) suff.ranges.push_back({splitl, root - 1, yinter + slope * (root - splitl) - suff.lazy, slope});
}

void solve(int l, int r, Cell &pref, Cell &suff) {
	pref.lazy = suff.lazy = 0;
	if(l <= r) {
		int root = queryRmq(l, r);
		
		Cell stSuff, stPref;
		Cell drSuff, drPref;
		
		solve(l, root - 1, stPref, stSuff);
		solve(root + 1, r, drPref, drSuff);
		//printf("-------------%d %d %d------------\n", l, r, root);
		
		for(auto it: queries[root])
			rez[it.i] = min(drPref.getDp(it.r) + (long long)(root - it.l + 1) * h[root],
			                stSuff.getDp(it.l) + (long long)(it.r - root + 1) * h[root]);
	
		prefCompress(drPref, root, stPref.getDp(root - 1) + h[root], h[root], (long long)(root - l + 1) * h[root]);
		suffCompress(stSuff, root, drSuff.getDp(root + 1) + h[root], h[root], (long long)(r - root + 1) * h[root]);

		stPref.ranges.push_back({root, root, stPref.getDp(root - 1) + h[root] - stPref.lazy, 1});
		drSuff.ranges.push_front({root, root, drSuff.getDp(root + 1) + h[root] - drSuff.lazy, -1});

		heavyMerge(stPref, drPref, pref);
		heavyMerge(stSuff, drSuff, suff);
		
		//printf("Suffix sum:\n");
		//for(auto it: suff.ranges)
		//	printf("Range: %d %d; Function %d+%dx\n", it.l, it.r, it.yinter + suff.lazy, it.slope);
		//printf("Prefix sum:\n");
		//for(auto it: pref.ranges)
		//	printf("Range: %d %d; Function %d+%dx\n", it.l, it.r, it.yinter + pref.lazy, it.slope);
	}
}

void solveQueries(int n) {
	Cell st, dr;
	solve(0, n - 1, st, dr);
}

vector<long long> minimum_costs(vector<int> _h, vector<int> l, vector<int> r) {
	int n, q;
	
	h = _h;
	n = _h.size();
	q = l.size();
	rez.resize(q);

	for(int i = 0; i < n; ++i)
		rmq[0][i] = i;
	for(int i = 2; i <= n; ++i)
		rmqlg[i] = rmqlg[i / 2] + 1;
	
	for(int l = 1; l < MAX_L; ++l)
		for(int i = 0; i < n - (1 << l) + 1; ++i)
			rmq[l][i] = argmax(rmq[l - 1][i], rmq[l - 1][i + (1 << (l - 1))]);

	for(int i = 0; i < q; ++i) {
		int root = queryRmq(l[i], r[i]);
		queries[root].push_back({l[i], r[i], i});
	}

	solveQueries(n);

	return rez;
}

Compilation message (stderr)

meetings.cpp: In function 'void heavyMerge(Cell&, Cell&, Cell&)':
meetings.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < dr.ranges.size(); ++i) {
                  ~~^~~~~~~~~~~~~~~~~~

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