Submission #91505

#	Time	Username	Problem	Language	Result	Execution time	Memory
91505		tincamatei	Meetings (IOI18_meetings)	C++14	60 / 100	5594 ms	243576 KiB

meetings

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

using namespace std;

vector<int> h;

const int MAX_L = 20;
const int MAX_N = 750000;

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;
}

void initrmq(int n) {
	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))]);
}

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 RangeSet {
	set<int> x;
	long long lazy[1+4*MAX_N];
	int rangeR[MAX_N];
	long long yinter[MAX_N];
	long long slope[MAX_N];

	void clear() {
		for(int i = 0; i <= 4*MAX_N; ++i)
			lazy[i] = 0;
		for(int i = 0; i < MAX_N; ++i)
			rangeR[i] = yinter[i] = slope[i] = 0;
	}

	void pushlazy(int nod, int l, int r) {
		if(l == r)
			yinter[l] += lazy[nod];
		else {
			lazy[2 * nod] += lazy[nod];
			lazy[2 * nod + 1] += lazy[nod];
		}
		lazy[nod] = 0;
	}

	void getlazy(int poz, int l = 0, int r = MAX_N - 1, int nod = 1) {
		if(r < poz || poz < l || r < l) return;
		pushlazy(nod, l, r);
		if(l < r) {
			int mid = (l + r) / 2;
			getlazy(poz, l, mid, 2 * nod);
			getlazy(poz, mid + 1, r, 2 * nod + 1);
		}
	}

	void addRange(int i, int j, long long val, int l = 0, int r = MAX_N - 1, int nod = 1) {
		if(r < i || j < l || j < i || r < l) return;
		if(i <= l && r <= j)
			lazy[nod] += val;
		else {
			int mid = (l + r) / 2;
			addRange(i, j, val, l, mid, 2 * nod);
			addRange(i, j, val, mid + 1, r, 2 * nod + 1);
		}
	}

	void insertRange(int st, int dr, long long yinterU, long long slopeU) {
		getlazy(st);
		rangeR[st] = dr;
		yinter[st] = yinterU;
		slope[st] = slopeU;
		
		x.insert(st);
	}

	void eraseRange(int st) {
		x.erase(st);
	}

	long long getDp(int i) {
		if(x.size() == 0) return 0LL;
		set<int>::iterator it = x.upper_bound(i);
		if(it == x.begin()) return 0LL;
		it--;
		
		if(rangeR[*it] < i) return 0LL;

		getlazy(*it);
		return yinter[*it] + (i - *it) * slope[*it];
	}
} ranges;

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

vector<Query> queries[MAX_N];
vector<long long> rezq;
int ctreeL[MAX_N], ctreeR[MAX_N];

int buildctree(int l, int r) {
	if(l <= r) {
		int root = queryRmq(l, r);
		
		ctreeL[root] = buildctree(l, root - 1);
		ctreeR[root] = buildctree(root + 1, r);

		return root;
	}
	return -1;
}

void compress(int nod, int r, long long yinter, long long slope, long long cst) {
	int i = nod + 1;
	while(i <= r && slope * (ranges.rangeR[i] - nod) + yinter <=
	               ranges.getDp(ranges.rangeR[i]) + cst) {
		ranges.eraseRange(i);
		i = ranges.rangeR[i] + 1;
	}
	if(i <= r && slope * (i - nod) + yinter <= ranges.getDp(i) + cst) {
		int st = i, dr = ranges.rangeR[i];
		while(dr - st > 1) {
			int mid = (dr + st) / 2;
			if(slope * (mid - nod) + yinter <= 
			   ranges.slope[i] * (mid - i) + ranges.yinter[i] + cst)
				st = mid;
			else
				dr = mid;
		}

		long long dp = ranges.getDp(dr);
		ranges.eraseRange(i);
		ranges.insertRange(dr, ranges.rangeR[i], dp, ranges.slope[i]);
		i = dr;
	}

	if(nod + 1 <= i - 1) ranges.insertRange(nod + 1, i - 1, yinter + slope, slope);
	ranges.addRange(i, r, cst);
}

void ctreedfs(int nod, int l, int r) {
	if(nod != -1) {
		ctreedfs(ctreeL[nod], l, nod - 1);
		ctreedfs(ctreeR[nod], nod + 1, r);
		

		for(auto it: queries[nod])
			rezq[it.i] = min(rezq[it.i],
			                 ranges.getDp(it.r) + (long long)h[nod] * (nod - it.l + 1));
	
		compress(nod, r, ranges.getDp(nod - 1) + h[nod], h[nod], (long long)(nod - l + 1) * h[nod]);
		ranges.insertRange(nod, nod, ranges.getDp(nod - 1) + h[nod], 0);
	}
}

void solve(int n, int q, const vector<int> &l, const vector<int> &r) {
	initrmq(n);
	
	for(int i = 0; i < n; ++i)
		queries[i].clear();

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

	ranges.clear();

	int root = buildctree(0, n - 1);
	
	ctreedfs(root, 0, n - 1);
}

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

	rezq.resize(q, 1LL << 60);

	solve(n, q, l, r);
	reverse(h.begin(), h.end());
	for(int i = 0; i < q; ++i) {
		swap(l[i], r[i]);
		l[i] = n - 1 - l[i];
		r[i] = n - 1 - r[i];
	}
	solve(n, q, l, r);

	return rezq;
}

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