oj.uz

Submission #145915

# Submission time Handle Problem Language Result Execution time Memory
145915 2019-08-21T11:04:45 Z Minnakhmetov Meetings (IOI18_meetings) C++14
19 / 100
 777 ms 349492 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;
	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 build(x - 1, l, r) - (r - l + 1);

	ll mn = min(build(x - 1, l, occ[x][fo] - 1), build(x - 1, occ[x][lo] + 1, r));
	for (int i = fo; i < lo; i++) {
		ll res = build(x - 1, occ[x][fo] + 1, occ[x][lo] - 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);
}

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++) {
		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);

	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 128 ms 95196 KB Output is correct
3 Correct 129 ms 95096 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 130 ms 95072 KB Output is correct
6 Correct 132 ms 95040 KB Output is correct
7 Correct 141 ms 95260 KB Output is correct
8 Correct 138 ms 95196 KB Output is correct
9 Correct 128 ms 95096 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 128 ms 95196 KB Output is correct
3 Correct 129 ms 95096 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 130 ms 95072 KB Output is correct
6 Correct 132 ms 95040 KB Output is correct
7 Correct 141 ms 95260 KB Output is correct
8 Correct 138 ms 95196 KB Output is correct
9 Correct 128 ms 95096 KB Output is correct
10 Correct 715 ms 234752 KB Output is correct
11 Correct 777 ms 234924 KB Output is correct
12 Correct 551 ms 234716 KB Output is correct
13 Correct 754 ms 234700 KB Output is correct
14 Correct 557 ms 234772 KB Output is correct
15 Correct 545 ms 234716 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 Runtime error 374 ms 349492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 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 Runtime error 374 ms 349492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 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 128 ms 95196 KB Output is correct
3 Correct 129 ms 95096 KB Output is correct
4 Correct 126 ms 95096 KB Output is correct
5 Correct 130 ms 95072 KB Output is correct
6 Correct 132 ms 95040 KB Output is correct
7 Correct 141 ms 95260 KB Output is correct
8 Correct 138 ms 95196 KB Output is correct
9 Correct 128 ms 95096 KB Output is correct
10 Correct 715 ms 234752 KB Output is correct
11 Correct 777 ms 234924 KB Output is correct
12 Correct 551 ms 234716 KB Output is correct
13 Correct 754 ms 234700 KB Output is correct
14 Correct 557 ms 234772 KB Output is correct
15 Correct 545 ms 234716 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Runtime error 374 ms 349492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -