#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
if (N <= 5000 && Q <= 5000) {
vector<ll> ans(Q, inf);
for (int i = 0; i < Q; i++) {
vector<int> stk;
vector<ll> A(N);
for (int j = L[i]; j <= R[i]; j++) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
A[j] = 1LL * H[j] * (j - (L[i] - 1));
} else {
A[j] = 1LL * H[j] * (j - stk.back()) + A[stk.back()];
}
stk.push_back(j);
}
stk.clear();
vector<ll> B(N);
for (int j = R[i]; j >= L[i]; j--) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
B[j] = 1LL * H[j] * ((R[i] + 1) - j);
} else {
B[j] = 1LL * H[j] * (stk.back() - j) + B[stk.back()];
}
stk.push_back(j);
}
for (int j = L[i]; j <= R[i]; j++) {
ans[i] = min(ans[i], A[j] + B[j] - H[j]);
}
}
return ans;
}
vector LC(N, vector<int>(21, -1));
for (int i = 0; i < N; i++) {
if (i) {
LC[i] = LC[i - 1];
}
LC[i][H[i]] = i;
}
vector RC(N, vector<int>(21, N));
for (int i = N - 1; i >= 0; i--) {
if (i < N - 1) {
RC[i] = RC[i + 1];
}
RC[i][H[i]] = i;
}
vector<int> LS(N), LP(N), stk;
for (int i = 0; i < N; i++) {
while (!stk.empty() && H[stk.back()] <= H[i]) {
stk.pop_back();
}
if (stk.empty()) {
LP[i] = -1;
LS[i] = H[i] * (i + 1);
} else {
LP[i] = stk.back();
LS[i] = H[i] * (i - LP[i]) + LS[LP[i]];
}
stk.push_back(i);
}
vector<int> RS(N), RP(N); stk.clear();
for (int i = N - 1; i >= 0; i--) {
while (!stk.empty() && H[stk.back()] <= H[i]) {
stk.pop_back();
}
if (stk.empty()) {
RP[i] = N;
RS[i] = H[i] * (N - i);
} else {
RP[i] = stk.back();
RS[i] = H[i] * (RP[i] - i) + RS[RP[i]];
}
stk.push_back(i);
}
vector<int> lg(N + 1);
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
vector st(N, vector<int>(lg[N] + 1));
for (int i = 0; i < N; i++) {
st[i][0] = LS[i] + RS[i] - H[i];
}
for (int j = 0; j < lg[N]; j++) {
for (int i = 0; i + (2 << j) <= N; i++) {
st[i][j + 1] = min(st[i][j], st[i + (1 << j)][j]);
}
}
auto query = [&](int l, int r) {
int k = lg[r - l];
return min(st[l][k], st[r - (1 << k)][k]);
};
vector<ll> ans(Q, 1e18);
for (int q = 0; q < Q; q++) {
for (int a = 1; a <= 20; a++) {
for (int b = 1; b <= 20; b++) {
int pa = RC[L[q]][a];
int pb = LC[R[q]][b];
if (pa > R[q] || pb < L[q] || LP[pa] >= L[q] || RP[pb] <= R[q]) {
continue;
}
int l = max(pa, LP[pb] + 1);
int r = min(pb, RP[pa] - 1);
if (l > r) {
continue;
}
int s = query(l, r + 1);
if (LP[pa] == -1) {
s -= a * L[q];
} else {
s -= a * (L[q] - 1 - LP[pa]);
s -= LS[LP[pa]];
}
if (RP[pb] == N) {
s -= b * (N - 1 - R[q]);
} else {
s -= b * (RP[pb] - 1 - R[q]);
s -= RS[RP[pb]];
}
ans[q] = min(ans[q], 1ll * s);
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
312 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
312 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
134 ms |
616 KB |
Output is correct |
11 |
Correct |
491 ms |
616 KB |
Output is correct |
12 |
Correct |
149 ms |
620 KB |
Output is correct |
13 |
Correct |
493 ms |
616 KB |
Output is correct |
14 |
Correct |
60 ms |
624 KB |
Output is correct |
15 |
Correct |
73 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
36 ms |
4928 KB |
Output is correct |
3 |
Correct |
154 ms |
41048 KB |
Output is correct |
4 |
Correct |
147 ms |
41052 KB |
Output is correct |
5 |
Correct |
150 ms |
41056 KB |
Output is correct |
6 |
Correct |
142 ms |
41036 KB |
Output is correct |
7 |
Correct |
162 ms |
41092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
36 ms |
4928 KB |
Output is correct |
3 |
Correct |
154 ms |
41048 KB |
Output is correct |
4 |
Correct |
147 ms |
41052 KB |
Output is correct |
5 |
Correct |
150 ms |
41056 KB |
Output is correct |
6 |
Correct |
142 ms |
41036 KB |
Output is correct |
7 |
Correct |
162 ms |
41092 KB |
Output is correct |
8 |
Correct |
189 ms |
41052 KB |
Output is correct |
9 |
Correct |
118 ms |
41036 KB |
Output is correct |
10 |
Correct |
188 ms |
41164 KB |
Output is correct |
11 |
Correct |
207 ms |
41092 KB |
Output is correct |
12 |
Correct |
122 ms |
40968 KB |
Output is correct |
13 |
Correct |
245 ms |
41060 KB |
Output is correct |
14 |
Correct |
162 ms |
41000 KB |
Output is correct |
15 |
Correct |
277 ms |
41008 KB |
Output is correct |
16 |
Correct |
215 ms |
41100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
312 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
134 ms |
616 KB |
Output is correct |
11 |
Correct |
491 ms |
616 KB |
Output is correct |
12 |
Correct |
149 ms |
620 KB |
Output is correct |
13 |
Correct |
493 ms |
616 KB |
Output is correct |
14 |
Correct |
60 ms |
624 KB |
Output is correct |
15 |
Correct |
73 ms |
632 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
36 ms |
4928 KB |
Output is correct |
18 |
Correct |
154 ms |
41048 KB |
Output is correct |
19 |
Correct |
147 ms |
41052 KB |
Output is correct |
20 |
Correct |
150 ms |
41056 KB |
Output is correct |
21 |
Correct |
142 ms |
41036 KB |
Output is correct |
22 |
Correct |
162 ms |
41092 KB |
Output is correct |
23 |
Correct |
189 ms |
41052 KB |
Output is correct |
24 |
Correct |
118 ms |
41036 KB |
Output is correct |
25 |
Correct |
188 ms |
41164 KB |
Output is correct |
26 |
Correct |
207 ms |
41092 KB |
Output is correct |
27 |
Correct |
122 ms |
40968 KB |
Output is correct |
28 |
Correct |
245 ms |
41060 KB |
Output is correct |
29 |
Correct |
162 ms |
41000 KB |
Output is correct |
30 |
Correct |
277 ms |
41008 KB |
Output is correct |
31 |
Correct |
215 ms |
41100 KB |
Output is correct |
32 |
Runtime error |
325 ms |
233372 KB |
Execution killed with signal 11 |
33 |
Halted |
0 ms |
0 KB |
- |