oj.uz

Submission #145924

# Submission time Handle Problem Language Result Execution time Memory
145924 2019-08-21T11:30:56 Z Minnakhmetov Meetings (IOI18_meetings) C++14
19 / 100
 776 ms 234744 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;
	if (fo == lo)
		return build(x - 1, l, r) - (r - l + 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 - 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);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 126 ms 95116 KB Output is correct
3 Correct 126 ms 95224 KB Output is correct
4 Correct 129 ms 95068 KB Output is correct
5 Correct 129 ms 95100 KB Output is correct
6 Correct 153 ms 95096 KB Output is correct
7 Correct 157 ms 95028 KB Output is correct
8 Correct 162 ms 95096 KB Output is correct
9 Correct 151 ms 95148 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 126 ms 95116 KB Output is correct
3 Correct 126 ms 95224 KB Output is correct
4 Correct 129 ms 95068 KB Output is correct
5 Correct 129 ms 95100 KB Output is correct
6 Correct 153 ms 95096 KB Output is correct
7 Correct 157 ms 95028 KB Output is correct
8 Correct 162 ms 95096 KB Output is correct
9 Correct 151 ms 95148 KB Output is correct
10 Correct 568 ms 234608 KB Output is correct
11 Correct 744 ms 234716 KB Output is correct
12 Correct 548 ms 234616 KB Output is correct
13 Correct 776 ms 234676 KB Output is correct
14 Correct 537 ms 234620 KB Output is correct
15 Correct 543 ms 234744 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 79 ms 2936 KB Output is correct
3 Correct 236 ms 14100 KB Output is correct
4 Incorrect 284 ms 11472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 79 ms 2936 KB Output is correct
3 Correct 236 ms 14100 KB Output is correct
4 Incorrect 284 ms 11472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 126 ms 95116 KB Output is correct
3 Correct 126 ms 95224 KB Output is correct
4 Correct 129 ms 95068 KB Output is correct
5 Correct 129 ms 95100 KB Output is correct
6 Correct 153 ms 95096 KB Output is correct
7 Correct 157 ms 95028 KB Output is correct
8 Correct 162 ms 95096 KB Output is correct
9 Correct 151 ms 95148 KB Output is correct
10 Correct 568 ms 234608 KB Output is correct
11 Correct 744 ms 234716 KB Output is correct
12 Correct 548 ms 234616 KB Output is correct
13 Correct 776 ms 234676 KB Output is correct
14 Correct 537 ms 234620 KB Output is correct
15 Correct 543 ms 234744 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 79 ms 2936 KB Output is correct
18 Correct 236 ms 14100 KB Output is correct
19 Incorrect 284 ms 11472 KB Output isn't correct
20 Halted 0 ms 0 KB -