Submission #145928

# Submission time Handle Problem Language Result Execution time Memory
145928 2019-08-21T11:37:43 Z Minnakhmetov Meetings (IOI18_meetings) C++14
19 / 100
777 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[a[i]].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);
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 127 ms 95152 KB Output is correct
3 Correct 129 ms 95068 KB Output is correct
4 Correct 128 ms 95164 KB Output is correct
5 Correct 130 ms 95156 KB Output is correct
6 Correct 126 ms 95096 KB Output is correct
7 Correct 132 ms 95096 KB Output is correct
8 Correct 127 ms 95096 KB Output is correct
9 Correct 126 ms 95068 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 127 ms 95152 KB Output is correct
3 Correct 129 ms 95068 KB Output is correct
4 Correct 128 ms 95164 KB Output is correct
5 Correct 130 ms 95156 KB Output is correct
6 Correct 126 ms 95096 KB Output is correct
7 Correct 132 ms 95096 KB Output is correct
8 Correct 127 ms 95096 KB Output is correct
9 Correct 126 ms 95068 KB Output is correct
10 Correct 544 ms 234592 KB Output is correct
11 Correct 777 ms 234788 KB Output is correct
12 Correct 644 ms 234616 KB Output is correct
13 Correct 739 ms 234592 KB Output is correct
14 Correct 550 ms 234628 KB Output is correct
15 Correct 547 ms 234616 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 95 ms 2936 KB Output is correct
3 Incorrect 282 ms 14260 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 95 ms 2936 KB Output is correct
3 Incorrect 282 ms 14260 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 127 ms 95152 KB Output is correct
3 Correct 129 ms 95068 KB Output is correct
4 Correct 128 ms 95164 KB Output is correct
5 Correct 130 ms 95156 KB Output is correct
6 Correct 126 ms 95096 KB Output is correct
7 Correct 132 ms 95096 KB Output is correct
8 Correct 127 ms 95096 KB Output is correct
9 Correct 126 ms 95068 KB Output is correct
10 Correct 544 ms 234592 KB Output is correct
11 Correct 777 ms 234788 KB Output is correct
12 Correct 644 ms 234616 KB Output is correct
13 Correct 739 ms 234592 KB Output is correct
14 Correct 550 ms 234628 KB Output is correct
15 Correct 547 ms 234616 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 95 ms 2936 KB Output is correct
18 Incorrect 282 ms 14260 KB Output isn't correct
19 Halted 0 ms 0 KB -