oj.uz

Submission #145930

# Submission time Handle Problem Language Result Execution time Memory
145930 2019-08-21T11:51:30 Z Minnakhmetov Meetings (IOI18_meetings) C++14
36 / 100
 5500 ms 234788 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
const ll INF = 1e18;
const int N1 = 5005, N2 = 1e5 + 5, K = 21;
ll lp[N1][N1], rp[N1][N1], seg_val[K][N2];
int n, q;
vector<int> a, occ[K];
 
vector<ll> slow(vector<int> L, vector<int> R) {
	for (int i = 0; i < n; i++) {
  		ll cur = 0;
  		int mx = a[i];
  		for (int j = i - 1; j >= 0; j--) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			lp[j][i] = cur;
  		}
 
  		cur = 0;
  		mx = a[i];
 
  		for (int j = i + 1; j < n; j++) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			rp[i][j] = cur;
  		}
  	}
 
 
  	vector<ll> ans(q);
 
  	for (int i = 0; i < q; i++) {
  		ll mn = INF;
  		for (int j = L[i]; j <= R[i]; j++) {
  			mn = min(mn, lp[L[i]][j] + rp[j][R[i]] + a[j]);
  		}
  		ans[i] = mn;
  	}
  	return ans;
}
 
 
 
struct ST {
	ll t[N2 * 4];
	void build(int v, int L, int R, ll val[N2]) {
		if (L == R) {
			t[v] = val[L];
		}
		else {
			int m = (L + R) >> 1;
			build(v * 2, L, m, val);
			build(v * 2 + 1, m + 1, R, val);
			t[v] = min(t[v * 2], t[v * 2 + 1]);
		}
	}
	ll que(int l, int r, int v, int L, int R) {
		if (l > r)
			return INF;
		if (l == L && r == R) {
			return t[v];
		}
		int m = (L + R) >> 1;
		return min(que(l, min(m, r), v * 2, L, m),
			que(max(m + 1, l), r, v * 2 + 1, m + 1, R));
	}
} tr[K];
 
ll build(int x, int l, int r) {
	if (l > r)
		return 0;
	// cout << x << " " << l << " " << r << endl;
	int fo = lower_bound(all(occ[x]), l - 1) - occ[x].begin(),
		lo = upper_bound(all(occ[x]), r) - occ[x].begin() - 1;
 
	ll mn = INF;
 
	for (int i = fo; i <= lo; i++) {
		ll res = build(x - 1, occ[x][i] + 1, occ[x][i + 1] - 1);
		seg_val[x][i] = res;
		mn = min(mn, res);
	}
 
	// cout << x << " " << l << " " << r << " " << mn + (r - l + 1) * x << "\n";
 
	return mn - (r - l + 1);
}
 
ll que(int x, int l, int r) {
	if (l > r)
		return 0;
	int fo = lower_bound(all(occ[x]), l) - occ[x].begin(),
		lo = upper_bound(all(occ[x]), r) - occ[x].begin() - 1;
	if (fo > lo)
		return que(x - 1, l, r) - (r - l + 1);
	ll mn = min(que(x - 1, l, occ[x][fo] - 1), que(x - 1, occ[x][lo] + 1, r));
	mn = min(mn, tr[x].que(fo, lo - 1, 1, 0, occ[x].size() - 1));
 
	// cout << x << " " << l << " " << r << " " << mn + (r - l + 1) * x << "\n";
 
	return mn - (r - l + 1);
}
 
// ll que(int x, int l, int r) {
// 	if (l > r)
// 		return 0;
// 	int fo = lower_bound(all(occ[x]), l - 1) - occ[x].begin(),
// 		lo = upper_bound(all(occ[x]), r) - occ[x].begin() - 1;
 
// 	if (fo > lo)
// 		return que(x - 1, l, r) - (r - l + 1);
 
// 	if (occ[x][lo + 1] == r + 1)
// 		lo++;
 
// 	ll mn = min(que(x - 1, l, occ[x][fo] - 1), que(x - 1, occ[x][lo] + 1, r));
// 	mn = min(mn, tr[x].que(fo, lo - 1, 1, 0, occ[x].size() - 1));
 
// 	// cout << x << " " << l << " " << r << " " << mn + (r - l + 1) * x << "\n";
 
// 	return mn - (r - l + 1);
// }
 
vector<ll> solveWhenLessThan20(vector<int> L, vector<int> R) {
	vector<ll> ans(q, 0);
 
	for (int i = 0; i < K; i++) {
		occ[i].push_back(-1);
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= a[i]; j++)
			occ[j].push_back(i);
	}
 
 
	for (int i = 0; i < K; i++) {
		occ[i].push_back(n);
		fill(seg_val[i], seg_val[i] + occ[i].size(), INF);
	}
 
 
 
	build(K - 1, 0, n - 1);
 
	// return ans;
 
 
 
	for (int i = 0; i < K; i++) {
		tr[i].build(1, 0, occ[i].size() - 1, seg_val[i]);
	}
 
	for (int i = 0; i < q; i++) {
		ans[i] = que(K - 1, L[i], R[i]) + (R[i] - L[i] + 1) * K;
	}
 
	return ans;
}
 
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	a = H;
	n = a.size(), q = L.size();
 
  	if (n < N1 && q < N1) {
  		return slow(L, R); 
  	}
 
  	return solveWhenLessThan20(L, R);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 130 ms 95100 KB Output is correct
3 Correct 141 ms 95224 KB Output is correct
4 Correct 159 ms 95096 KB Output is correct
5 Correct 141 ms 95224 KB Output is correct
6 Correct 132 ms 95096 KB Output is correct
7 Correct 129 ms 95096 KB Output is correct
8 Correct 130 ms 95224 KB Output is correct
9 Correct 131 ms 95096 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 130 ms 95100 KB Output is correct
3 Correct 141 ms 95224 KB Output is correct
4 Correct 159 ms 95096 KB Output is correct
5 Correct 141 ms 95224 KB Output is correct
6 Correct 132 ms 95096 KB Output is correct
7 Correct 129 ms 95096 KB Output is correct
8 Correct 130 ms 95224 KB Output is correct
9 Correct 131 ms 95096 KB Output is correct
10 Correct 578 ms 234704 KB Output is correct
11 Correct 771 ms 234672 KB Output is correct
12 Correct 555 ms 234788 KB Output is correct
13 Correct 748 ms 234788 KB Output is correct
14 Correct 553 ms 234752 KB Output is correct
15 Correct 558 ms 234612 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 80 ms 2936 KB Output is correct
3 Correct 232 ms 13292 KB Output is correct
4 Correct 271 ms 11564 KB Output is correct
5 Correct 140 ms 13416 KB Output is correct
6 Correct 194 ms 13136 KB Output is correct
7 Correct 202 ms 13292 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 80 ms 2936 KB Output is correct
3 Correct 232 ms 13292 KB Output is correct
4 Correct 271 ms 11564 KB Output is correct
5 Correct 140 ms 13416 KB Output is correct
6 Correct 194 ms 13136 KB Output is correct
7 Correct 202 ms 13292 KB Output is correct
8 Correct 1825 ms 44856 KB Output is correct
9 Correct 1153 ms 45076 KB Output is correct
10 Correct 1747 ms 44884 KB Output is correct
11 Correct 2894 ms 43320 KB Output is correct
12 Correct 1603 ms 43420 KB Output is correct
13 Correct 2549 ms 43284 KB Output is correct
14 Correct 555 ms 61392 KB Output is correct
15 Execution timed out 5551 ms 16620 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 130 ms 95100 KB Output is correct
3 Correct 141 ms 95224 KB Output is correct
4 Correct 159 ms 95096 KB Output is correct
5 Correct 141 ms 95224 KB Output is correct
6 Correct 132 ms 95096 KB Output is correct
7 Correct 129 ms 95096 KB Output is correct
8 Correct 130 ms 95224 KB Output is correct
9 Correct 131 ms 95096 KB Output is correct
10 Correct 578 ms 234704 KB Output is correct
11 Correct 771 ms 234672 KB Output is correct
12 Correct 555 ms 234788 KB Output is correct
13 Correct 748 ms 234788 KB Output is correct
14 Correct 553 ms 234752 KB Output is correct
15 Correct 558 ms 234612 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 80 ms 2936 KB Output is correct
18 Correct 232 ms 13292 KB Output is correct
19 Correct 271 ms 11564 KB Output is correct
20 Correct 140 ms 13416 KB Output is correct
21 Correct 194 ms 13136 KB Output is correct
22 Correct 202 ms 13292 KB Output is correct
23 Correct 1825 ms 44856 KB Output is correct
24 Correct 1153 ms 45076 KB Output is correct
25 Correct 1747 ms 44884 KB Output is correct
26 Correct 2894 ms 43320 KB Output is correct
27 Correct 1603 ms 43420 KB Output is correct
28 Correct 2549 ms 43284 KB Output is correct
29 Correct 555 ms 61392 KB Output is correct
30 Execution timed out 5551 ms 16620 KB Time limit exceeded
31 Halted 0 ms 0 KB -