oj.uz

Submission #91505

# Submission time Handle Problem Language Result Execution time Memory
91505 2018-12-27T21:59:21 Z tincamatei Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 243576 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56164 KB Output is correct
2 Correct 68 ms 56460 KB Output is correct
3 Correct 67 ms 56460 KB Output is correct
4 Correct 67 ms 56412 KB Output is correct
5 Correct 69 ms 56356 KB Output is correct
6 Correct 69 ms 56704 KB Output is correct
7 Correct 69 ms 56420 KB Output is correct
8 Correct 65 ms 56600 KB Output is correct
9 Correct 64 ms 56572 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56164 KB Output is correct
2 Correct 68 ms 56460 KB Output is correct
3 Correct 67 ms 56460 KB Output is correct
4 Correct 67 ms 56412 KB Output is correct
5 Correct 69 ms 56356 KB Output is correct
6 Correct 69 ms 56704 KB Output is correct
7 Correct 69 ms 56420 KB Output is correct
8 Correct 65 ms 56600 KB Output is correct
9 Correct 64 ms 56572 KB Output is correct
10 Correct 79 ms 56924 KB Output is correct
11 Correct 76 ms 56952 KB Output is correct
12 Correct 77 ms 56924 KB Output is correct
13 Correct 76 ms 56920 KB Output is correct
14 Correct 81 ms 57400 KB Output is correct
15 Correct 76 ms 56892 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 56224 KB Output is correct
2 Correct 136 ms 60436 KB Output is correct
3 Correct 579 ms 78560 KB Output is correct
4 Correct 391 ms 71152 KB Output is correct
5 Correct 564 ms 79048 KB Output is correct
6 Correct 469 ms 78276 KB Output is correct
7 Correct 433 ms 80368 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 56224 KB Output is correct
2 Correct 136 ms 60436 KB Output is correct
3 Correct 579 ms 78560 KB Output is correct
4 Correct 391 ms 71152 KB Output is correct
5 Correct 564 ms 79048 KB Output is correct
6 Correct 469 ms 78276 KB Output is correct
7 Correct 433 ms 80368 KB Output is correct
8 Correct 531 ms 73308 KB Output is correct
9 Correct 487 ms 73048 KB Output is correct
10 Correct 514 ms 73384 KB Output is correct
11 Correct 479 ms 71388 KB Output is correct
12 Correct 455 ms 71044 KB Output is correct
13 Correct 468 ms 71928 KB Output is correct
14 Correct 572 ms 79720 KB Output is correct
15 Correct 402 ms 71116 KB Output is correct
16 Correct 468 ms 77536 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56164 KB Output is correct
2 Correct 68 ms 56460 KB Output is correct
3 Correct 67 ms 56460 KB Output is correct
4 Correct 67 ms 56412 KB Output is correct
5 Correct 69 ms 56356 KB Output is correct
6 Correct 69 ms 56704 KB Output is correct
7 Correct 69 ms 56420 KB Output is correct
8 Correct 65 ms 56600 KB Output is correct
9 Correct 64 ms 56572 KB Output is correct
10 Correct 79 ms 56924 KB Output is correct
11 Correct 76 ms 56952 KB Output is correct
12 Correct 77 ms 56924 KB Output is correct
13 Correct 76 ms 56920 KB Output is correct
14 Correct 81 ms 57400 KB Output is correct
15 Correct 76 ms 56892 KB Output is correct
16 Correct 58 ms 56224 KB Output is correct
17 Correct 136 ms 60436 KB Output is correct
18 Correct 579 ms 78560 KB Output is correct
19 Correct 391 ms 71152 KB Output is correct
20 Correct 564 ms 79048 KB Output is correct
21 Correct 469 ms 78276 KB Output is correct
22 Correct 433 ms 80368 KB Output is correct
23 Correct 531 ms 73308 KB Output is correct
24 Correct 487 ms 73048 KB Output is correct
25 Correct 514 ms 73384 KB Output is correct
26 Correct 479 ms 71388 KB Output is correct
27 Correct 455 ms 71044 KB Output is correct
28 Correct 468 ms 71928 KB Output is correct
29 Correct 572 ms 79720 KB Output is correct
30 Correct 402 ms 71116 KB Output is correct
31 Correct 468 ms 77536 KB Output is correct
32 Correct 3310 ms 176760 KB Output is correct
33 Correct 2921 ms 173348 KB Output is correct
34 Correct 3308 ms 181628 KB Output is correct
35 Correct 3750 ms 181336 KB Output is correct
36 Correct 3164 ms 180212 KB Output is correct
37 Correct 3485 ms 183156 KB Output is correct
38 Correct 5206 ms 243576 KB Output is correct
39 Execution timed out 5594 ms 242796 KB Time limit exceeded
40 Halted 0 ms 0 KB -