oj.uz

Submission #145919

# Submission time Handle Problem Language Result Execution time Memory
145919 2019-08-21T11:16:53 Z Minnakhmetov Meetings (IOI18_meetings) C++14
17 / 100
 5500 ms 11128 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) - 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][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);
}

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

	// 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 77 ms 2424 KB Output is correct
3 Correct 229 ms 10400 KB Output is correct
4 Correct 261 ms 10224 KB Output is correct
5 Correct 136 ms 10396 KB Output is correct
6 Correct 185 ms 10396 KB Output is correct
7 Correct 189 ms 10224 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 77 ms 2424 KB Output is correct
3 Correct 229 ms 10400 KB Output is correct
4 Correct 261 ms 10224 KB Output is correct
5 Correct 136 ms 10396 KB Output is correct
6 Correct 185 ms 10396 KB Output is correct
7 Correct 189 ms 10224 KB Output is correct
8 Correct 1317 ms 11000 KB Output is correct
9 Correct 678 ms 11128 KB Output is correct
10 Correct 1229 ms 10872 KB Output is correct
11 Correct 2148 ms 10872 KB Output is correct
12 Correct 989 ms 10844 KB Output is correct
13 Correct 1825 ms 10872 KB Output is correct
14 Correct 351 ms 10612 KB Output is correct
15 Execution timed out 5528 ms 10424 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -