Submission #145931

#	Time	Username	Problem	Language	Result	Execution time	Memory
145931		Minnakhmetov	Meetings (IOI18_meetings)	C++14	60 / 100	768 ms	234832 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40