oj.uz

Submission #145931

# Submission time Handle Problem Language Result Execution time Memory
145931 2019-08-21T11:52:38 Z Minnakhmetov Meetings (IOI18_meetings) C++14
60 / 100
 768 ms 234832 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 2 ms 376 KB Output is correct
2 Correct 132 ms 95096 KB Output is correct
3 Correct 134 ms 95096 KB Output is correct
4 Correct 132 ms 95068 KB Output is correct
5 Correct 136 ms 95064 KB Output is correct
6 Correct 132 ms 95052 KB Output is correct
7 Correct 134 ms 95156 KB Output is correct
8 Correct 133 ms 95068 KB Output is correct
9 Correct 136 ms 95108 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 132 ms 95096 KB Output is correct
3 Correct 134 ms 95096 KB Output is correct
4 Correct 132 ms 95068 KB Output is correct
5 Correct 136 ms 95064 KB Output is correct
6 Correct 132 ms 95052 KB Output is correct
7 Correct 134 ms 95156 KB Output is correct
8 Correct 133 ms 95068 KB Output is correct
9 Correct 136 ms 95108 KB Output is correct
10 Correct 589 ms 234616 KB Output is correct
11 Correct 768 ms 234832 KB Output is correct
12 Correct 549 ms 234568 KB Output is correct
13 Correct 752 ms 234688 KB Output is correct
14 Correct 561 ms 234744 KB Output is correct
15 Correct 557 ms 234632 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 77 ms 2908 KB Output is correct
3 Correct 228 ms 13288 KB Output is correct
4 Correct 266 ms 11544 KB Output is correct
5 Correct 167 ms 13200 KB Output is correct
6 Correct 197 ms 13164 KB Output is correct
7 Correct 198 ms 13292 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 77 ms 2908 KB Output is correct
3 Correct 228 ms 13288 KB Output is correct
4 Correct 266 ms 11544 KB Output is correct
5 Correct 167 ms 13200 KB Output is correct
6 Correct 197 ms 13164 KB Output is correct
7 Correct 198 ms 13292 KB Output is correct
8 Correct 649 ms 44904 KB Output is correct
9 Correct 376 ms 44948 KB Output is correct
10 Correct 601 ms 44860 KB Output is correct
11 Correct 689 ms 43296 KB Output is correct
12 Correct 383 ms 43396 KB Output is correct
13 Correct 643 ms 43284 KB Output is correct
14 Correct 261 ms 61372 KB Output is correct
15 Correct 632 ms 16748 KB Output is correct
16 Correct 388 ms 46776 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 132 ms 95096 KB Output is correct
3 Correct 134 ms 95096 KB Output is correct
4 Correct 132 ms 95068 KB Output is correct
5 Correct 136 ms 95064 KB Output is correct
6 Correct 132 ms 95052 KB Output is correct
7 Correct 134 ms 95156 KB Output is correct
8 Correct 133 ms 95068 KB Output is correct
9 Correct 136 ms 95108 KB Output is correct
10 Correct 589 ms 234616 KB Output is correct
11 Correct 768 ms 234832 KB Output is correct
12 Correct 549 ms 234568 KB Output is correct
13 Correct 752 ms 234688 KB Output is correct
14 Correct 561 ms 234744 KB Output is correct
15 Correct 557 ms 234632 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 77 ms 2908 KB Output is correct
18 Correct 228 ms 13288 KB Output is correct
19 Correct 266 ms 11544 KB Output is correct
20 Correct 167 ms 13200 KB Output is correct
21 Correct 197 ms 13164 KB Output is correct
22 Correct 198 ms 13292 KB Output is correct
23 Correct 649 ms 44904 KB Output is correct
24 Correct 376 ms 44948 KB Output is correct
25 Correct 601 ms 44860 KB Output is correct
26 Correct 689 ms 43296 KB Output is correct
27 Correct 383 ms 43396 KB Output is correct
28 Correct 643 ms 43284 KB Output is correct
29 Correct 261 ms 61372 KB Output is correct
30 Correct 632 ms 16748 KB Output is correct
31 Correct 388 ms 46776 KB Output is correct
32 Runtime error 474 ms 84460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -