#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 90100;
int n, q, h[maxn], l[maxn], r[maxn];
vector<ll> ans;
array<int, 3> tree[2*maxn];
array<int, 3> merge(array<int, 3> a, array<int, 3> b) {
if(a[0] ^ b[0]) return a[0] > b[0] ? a : b;
return {a[0], min(a[1], b[1]), max(a[2], b[2])};
}
void upd(int p, int v) {
p += n;
for(tree[p] = {v, p-n, p-n}; p>>=1;) tree[p] = merge(tree[p<<1], tree[p<<1|1]);
}
array<int, 3> get(int l, int r) {
//cout << l << " " << r << '\n';
array<int, 3> res = {-1, 0, 0};
for(l += n, r += n+1; l < r; l>>=1, r>>=1) {
if(l&1) res = merge(res, tree[l++]);
if(r&1) res = merge(res, tree[--r]);
}
//cout << res[0] << " " << res[1] << " " << res[2] << '\n';
return res;
}
ll ma[21][2*maxn];
void upda(int t, int p, ll v) {
for(ma[t][p+=n] = v; p>>=1;) ma[t][p] = min(ma[t][p<<1], ma[t][p<<1|1]);
}
ll geta(int t, ll l, ll r) {
ll ans = 1ll<<55;
for(l += n, r += n+1; l < r; l>>=1, r>>=1) {
if(l&1) ans = min(ans, ma[t][l++]);
if(r&1) ans = min(ans, ma[t][--r]);
}
return ans;
}
const int C = 0;
map<pair<int, int>, ll> memo;
ll solve(int l, int r) {
if(r < l) return 0;
if(memo.count({l, r})) return memo[{l, r}];
auto [V, tl, tr] = get(l, r);
ll ans = min(V*1ll*(r-tl+1) + solve(l, tl-1), V*1ll*(tr-l+1) + solve(tr+1, r));
if(n > C) ans = min(ans, V*1ll*(r-l+1) + geta(V, tl, tr-1));
else ans = min(ans, V*1ll*(tl-l+1+r-tr+1) + solve(tl+1, tr-1));
//cout << l << " " << r << " " << V << " " << tl << " " << tr << " / " << ans << '\n';
return memo[{l, r}] = min(ans, V*1ll*(r-l+1));
}
ll fake(int l, int r) {
int c = 0, a = 0, d = (r-l+1)*2;
while(l <= r) {
if(h[l] == 1) c++;
else c = 0;
a = max(a, c);
l++;
}
return d - a;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
q = L.size();
n = H.size();
for(int i = 0; i < n; i++) {
h[i] = H[i];
l[i] = L[i];
r[i] = R[i];
}
ans.resize(q);
for(int i = 0; i < n; i++) upd(i, h[i]);
vector<int> lst(22, -1);
memset(ma, 0x1f, sizeof ma);
if(n > C) {
int totmx = 0;
for(int i = 0; i < n; i++) {
totmx = max(totmx, h[i]);
if(lst[h[i]] != -1) {
upda(h[i], lst[h[i]], -(i - lst[h[i]] - 1));//solve(lst[h[i]]+1, i-1) - h[i]*1ll*(i - lst[h[i]] - 1));
}
lst[h[i]] = i;
}
upda(totmx, lst[totmx], -(n - lst[totmx]));//solve(lst[totmx]+1, n-1) - totmx*1ll*(n - lst[totmx]));
int s = 0;
for(int i = n; i--;) {
if(h[i] == 1) s++;
else {
if(ma[2][n+i] != -s) {
//exit(-1);
}
s = 0;
}
}
}
//for(int i = 0; i < n; i++)
// for(int j = 0; j <= i; j++) {
// assert(solve(j, i) == fake(j, i));
// }
//for(int i = 0; i < n; i++) cout << geta(2, i, i) << " "; cout << '\n';
for(int i = 0; i < q; i++) ans[i] = solve(l[i], r[i]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
60412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
60412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
29952 KB |
Output is correct |
| 2 |
Incorrect |
52 ms |
32760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
29952 KB |
Output is correct |
| 2 |
Incorrect |
52 ms |
32760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
60412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
