oj.uz

Submission #145927

# Submission time Handle Problem Language Result Execution time Memory
145927 2019-08-21T11:36:29 Z Minnakhmetov Meetings (IOI18_meetings) C++14
19 / 100
 775 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;

	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 129 ms 95096 KB Output is correct
3 Correct 129 ms 95084 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 128 ms 95196 KB Output is correct
6 Correct 160 ms 95164 KB Output is correct
7 Correct 141 ms 95060 KB Output is correct
8 Correct 149 ms 95120 KB Output is correct
9 Correct 131 ms 95104 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 129 ms 95096 KB Output is correct
3 Correct 129 ms 95084 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 128 ms 95196 KB Output is correct
6 Correct 160 ms 95164 KB Output is correct
7 Correct 141 ms 95060 KB Output is correct
8 Correct 149 ms 95120 KB Output is correct
9 Correct 131 ms 95104 KB Output is correct
10 Correct 556 ms 234684 KB Output is correct
11 Correct 775 ms 234736 KB Output is correct
12 Correct 539 ms 234668 KB Output is correct
13 Correct 735 ms 234628 KB Output is correct
14 Correct 559 ms 234744 KB Output is correct
15 Correct 550 ms 234692 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 79 ms 3012 KB Output is correct
3 Incorrect 253 ms 14156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 79 ms 3012 KB Output is correct
3 Incorrect 253 ms 14156 KB Output isn't correct
4 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 129 ms 95096 KB Output is correct
3 Correct 129 ms 95084 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 128 ms 95196 KB Output is correct
6 Correct 160 ms 95164 KB Output is correct
7 Correct 141 ms 95060 KB Output is correct
8 Correct 149 ms 95120 KB Output is correct
9 Correct 131 ms 95104 KB Output is correct
10 Correct 556 ms 234684 KB Output is correct
11 Correct 775 ms 234736 KB Output is correct
12 Correct 539 ms 234668 KB Output is correct
13 Correct 735 ms 234628 KB Output is correct
14 Correct 559 ms 234744 KB Output is correct
15 Correct 550 ms 234692 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 79 ms 3012 KB Output is correct
18 Incorrect 253 ms 14156 KB Output isn't correct
19 Halted 0 ms 0 KB -