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