# include <bits/stdc++.h>
# include "meetings.h"
using namespace std;
const int N = 8e5 + 2;
const int M = 5e3 + 2;
long long a[M][M], t[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
if(tl == tr)
t[v] = val;
else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
upd(pos, val, v << 1, tl, tm);
else
upd(pos, val, v << 1 | 1, tm + 1, tr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
}
int get(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
if(l > tr || tl > r)
return 0;
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) >> 1;
return max(get(l, r, v << 1, tl, tm),
get(l, r, v << 1 | 1, tm + 1, tr));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
int n = H.size();
vector<long long> C(Q);
if(n <= 5000){
for(int i = 0; i < n; i ++){
a[i][i] = H[i];
for(int j = i - 1; j >= 0; j --)
a[i][j] = max(int(a[i][j + 1]), H[j]);
for(int j = i + 1; j < n; j ++)
a[i][j] = max(int(a[i][j - 1]), H[j]);
for(int j = 1; j < n; j ++)
a[i][j] += a[i][j - 1];
}
for(int i = 0; i < Q; i ++){
long long ret = 5e18;
for(int j = L[i]; j <= R[i]; j ++){
long long now = a[j][R[i]];
if(L[i])
now -= a[j][L[i] - 1];
ret = min(ret, now);
}
C[i] = ret;
}
} else {
vector < pair <int, int> > qe;
qe.push_back({-1, -1});
int q = 0;
for(int i = 0; i < n; i ++){
if(H[i] == 2)
continue;
int j = i;
while(j + 1 < n && H[j + 1] == 1)
j ++;
qe.push_back({i, j});
upd(++ q, j - i + 1);
i = j;
}
for(int i = 0; i < Q; i ++){
C[i] = (R[i] - L[i] + 1) * 2;
int mx = 0;
int lo = 1, hi = q;
while(hi - lo > 1){
int md = (lo + hi) >> 1;
if(qe[md].second >= L[i])
hi = md;
else
lo = md;
}
if(qe[lo].second >= L[i])
hi = lo;
if(qe[hi].second >= L[i] && qe[hi].first <= L[i]){
mx = min(qe[hi].second, R[i]) - L[i] + 1;
}
lo = 1, hi = q;
while(hi - lo > 1){
int md = (lo + hi) >> 1;
if(qe[md].first <= R[i])
lo = md;
else
hi = md;
}
if(qe[hi].first <= R[i])
lo = hi;
if(qe[lo].first <= R[i] && R[i] <= qe[lo].second)
mx = max(mx, R[i] - max(qe[lo].first, L[i]) + 1);
int l, r;
lo = 1, hi = q;
while(hi - lo > 1){
int md = (lo + hi) >> 1;
if(qe[md].first >= L[i])
hi = md;
else
lo = md;
}
if(qe[lo].first >= L[i])
hi = lo;
if(qe[hi].first < L[i])
hi ++;
l = hi;
lo = 1, hi = q;
while(hi - lo > 1){
int md = (lo + hi) >> 1;
if(qe[md].second <= R[i])
lo = md;
else
hi = md;
}
if(qe[hi].second <= R[i])
lo = hi;
if(qe[lo].second > R[i])
lo --;
r = lo;
if(l <= r && 1 <= l && r <= q)
mx = max(mx, get(l, r));
C[i] -= mx;
}
}
return C;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
109 ms |
82844 KB |
Output is correct |
3 |
Correct |
112 ms |
82852 KB |
Output is correct |
4 |
Correct |
110 ms |
82800 KB |
Output is correct |
5 |
Correct |
111 ms |
82772 KB |
Output is correct |
6 |
Correct |
109 ms |
82840 KB |
Output is correct |
7 |
Correct |
109 ms |
82808 KB |
Output is correct |
8 |
Correct |
111 ms |
82868 KB |
Output is correct |
9 |
Correct |
113 ms |
82856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
109 ms |
82844 KB |
Output is correct |
3 |
Correct |
112 ms |
82852 KB |
Output is correct |
4 |
Correct |
110 ms |
82800 KB |
Output is correct |
5 |
Correct |
111 ms |
82772 KB |
Output is correct |
6 |
Correct |
109 ms |
82840 KB |
Output is correct |
7 |
Correct |
109 ms |
82808 KB |
Output is correct |
8 |
Correct |
111 ms |
82868 KB |
Output is correct |
9 |
Correct |
113 ms |
82856 KB |
Output is correct |
10 |
Correct |
549 ms |
196348 KB |
Output is correct |
11 |
Correct |
740 ms |
196268 KB |
Output is correct |
12 |
Correct |
548 ms |
196280 KB |
Output is correct |
13 |
Correct |
735 ms |
196252 KB |
Output is correct |
14 |
Correct |
562 ms |
196300 KB |
Output is correct |
15 |
Correct |
561 ms |
196316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
46 ms |
1744 KB |
Output is correct |
3 |
Correct |
134 ms |
4364 KB |
Output is correct |
4 |
Correct |
92 ms |
3592 KB |
Output is correct |
5 |
Correct |
94 ms |
4368 KB |
Output is correct |
6 |
Correct |
65 ms |
3548 KB |
Output is correct |
7 |
Correct |
61 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
46 ms |
1744 KB |
Output is correct |
3 |
Correct |
134 ms |
4364 KB |
Output is correct |
4 |
Correct |
92 ms |
3592 KB |
Output is correct |
5 |
Correct |
94 ms |
4368 KB |
Output is correct |
6 |
Correct |
65 ms |
3548 KB |
Output is correct |
7 |
Correct |
61 ms |
3448 KB |
Output is correct |
8 |
Incorrect |
176 ms |
6224 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
109 ms |
82844 KB |
Output is correct |
3 |
Correct |
112 ms |
82852 KB |
Output is correct |
4 |
Correct |
110 ms |
82800 KB |
Output is correct |
5 |
Correct |
111 ms |
82772 KB |
Output is correct |
6 |
Correct |
109 ms |
82840 KB |
Output is correct |
7 |
Correct |
109 ms |
82808 KB |
Output is correct |
8 |
Correct |
111 ms |
82868 KB |
Output is correct |
9 |
Correct |
113 ms |
82856 KB |
Output is correct |
10 |
Correct |
549 ms |
196348 KB |
Output is correct |
11 |
Correct |
740 ms |
196268 KB |
Output is correct |
12 |
Correct |
548 ms |
196280 KB |
Output is correct |
13 |
Correct |
735 ms |
196252 KB |
Output is correct |
14 |
Correct |
562 ms |
196300 KB |
Output is correct |
15 |
Correct |
561 ms |
196316 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
46 ms |
1744 KB |
Output is correct |
18 |
Correct |
134 ms |
4364 KB |
Output is correct |
19 |
Correct |
92 ms |
3592 KB |
Output is correct |
20 |
Correct |
94 ms |
4368 KB |
Output is correct |
21 |
Correct |
65 ms |
3548 KB |
Output is correct |
22 |
Correct |
61 ms |
3448 KB |
Output is correct |
23 |
Incorrect |
176 ms |
6224 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |