#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define pi pair < int, int >
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
int t[4 * N], lz[4 * N];
int prv[N][22], nxt[N][22];
int pr[N][22], prc[N][22], total[N];
int a[N], ans[N];
int n, q;
pair < pi, int > qr[N];
vector < ll > ret;
void push (int v, int l, int r){
if (l != r){
lz[v + v] += lz[v];
lz[v + v + 1] += lz[v];
}
t[v] += lz[v];
lz[v] = 0;
}
void upd (int v, int l, int r, int ql, int qr, int val){
push(v, l, r);
if (r < ql || qr < l)
return;
if (ql <= l && r <= qr){
lz[v] += val;
push(v, l, r);
return;
}
int mid = (l + r) >> 1;
upd(v + v, l, mid, ql, qr, val);
upd(v + v + 1, mid + 1, r, ql, qr, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
int get (int v, int l, int r, int ql, int qr){
push(v, l, r);
if (r < ql || qr < l)
return INF;
if (ql <= l && r <= qr)
return t[v];
int mid = (l + r) >> 1;
return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}
void build (int v, int l, int r){
if (l == r){
int last = n + 1;
for (int j = 20; j >= 1; j--){
prc[l][j] = last - l;
if (last > nxt[l][j]){
pr[l][j] = (last - nxt[l][j]) * j;
t[v] += pr[l][j];
last = nxt[l][j];
}
}
total[l] = t[v];
last = 0;
for (int j = 20; j >= 1; j--){
if (last < prv[l][j]){
t[v] += (prv[l][j] - last) * j;
last = prv[l][j];
}
}
t[v] -= a[l];
}
else {
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
t[v] = min(t[v + v], t[v + v + 1]);
}
}
void change (int l){
int last = n + 1;
for (int j = 20; j >= 1; j--){
if (last > nxt[l][j]){
upd(1, 1, n, nxt[l][j], last - 1, -j);
last = nxt[l][j];
}
}
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
for (int i = 0; i < n; i++)
a[i + 1] = H[i];
for (int i = 1; i <= n; i++){
for (int j = 1; j <= 20; j++)
prv[i][j] = prv[i - 1][j];
prv[i][a[i]] = i;
}
for (int j = 1; j <= 20; j++)
nxt[n + 1][j] = n + 1;
for (int i = n; i >= 1; i--){
for (int j = 1; j <= 20; j++)
nxt[i][j] = nxt[i + 1][j];
nxt[i][a[i]] = i;
}
build(1, 1, n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 20; j++)
pr[i][j] += pr[i][j - 1];
for (int i = 0; i < q; i++)
qr[i + 1] = {{L[i] + 1, R[i] + 1}, i + 1};
sort(qr + 1, qr + 1 + q);
int l = 1;
for (int i = 1; i <= q; i++){
while (qr[i].fr.fr > l){
change(l);
l++;
}
int r = qr[i].fr.sc, last = l - 1, res = INF;
for (int j = 20; j >= 1; j--){
if (last < prv[r][j] && prv[r][j] >= l){
res = min(res, get(1, 1, n, last + 1, prv[r][j]) - (total[r + 1] - pr[r + 1][j] + prc[r + 1][j] * j));
last = prv[r][j];
}
}
ans[qr[i].sc] = res;
}
for (int i = 1; i <= q; i++)
ret.pb(1ll * ans[i]);
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
62 ms |
5872 KB |
Output is correct |
3 |
Correct |
268 ms |
45296 KB |
Output is correct |
4 |
Correct |
325 ms |
45160 KB |
Output is correct |
5 |
Correct |
190 ms |
45164 KB |
Output is correct |
6 |
Correct |
207 ms |
45292 KB |
Output is correct |
7 |
Correct |
268 ms |
45164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
62 ms |
5872 KB |
Output is correct |
3 |
Correct |
268 ms |
45296 KB |
Output is correct |
4 |
Correct |
325 ms |
45160 KB |
Output is correct |
5 |
Correct |
190 ms |
45164 KB |
Output is correct |
6 |
Correct |
207 ms |
45292 KB |
Output is correct |
7 |
Correct |
268 ms |
45164 KB |
Output is correct |
8 |
Correct |
418 ms |
45272 KB |
Output is correct |
9 |
Correct |
237 ms |
44396 KB |
Output is correct |
10 |
Correct |
354 ms |
45292 KB |
Output is correct |
11 |
Correct |
511 ms |
45252 KB |
Output is correct |
12 |
Correct |
258 ms |
44524 KB |
Output is correct |
13 |
Correct |
414 ms |
45260 KB |
Output is correct |
14 |
Correct |
286 ms |
45384 KB |
Output is correct |
15 |
Correct |
870 ms |
45248 KB |
Output is correct |
16 |
Correct |
866 ms |
45292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |