#include "meetings.h"
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
const int N = 750000, H = 19;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int aa[N], qu[N], pp[N], qq[N], n; long long dp[N], dq[N];
int ii[H + 1][N], hh[N + 1];
void build(int n) {
int h, i, j;
for (i = 0; i < n; i++)
ii[0][i] = i;
for (h = 1; h <= H; h++)
for (i = 0; i < n; i++)
ii[h][i] = ii[h - 1][(j = i + (1 << h - 1)) >= n || aa[ii[h - 1][i]] >= aa[ii[h - 1][j]] ? i : j];
for (i = 1, h = 0; i <= n; i++) {
while (1 << h + 1 <= i)
h++;
hh[i] = h;
}
}
int get(int l, int r) {
int h = hh[r - l + 1];
return ii[h][aa[ii[h][l]] >= aa[ii[h][r - (1 << h) + 1]] ? l : r - (1 << h) + 1];
}
long long A(int i, int l) {
int j = get(l, i);
return dp[i] - ((pp[j] == -1 ? 0 : dp[pp[j]]) + (long long) aa[j] * (l - pp[j] - 1)) + dq[i] - aa[i];
}
long long B(int i, int r) {
int j = get(i, r);
return dq[i] - ((qq[j] == n ? 0 : dq[qq[j]]) + (long long) aa[j] * (qq[j] - r - 1)) + dp[i] - aa[i];
}
int L(int i, int j) {
int lower = -1, upper = j + 1;
while (upper - lower > 1) {
int l = (lower + upper) / 2;
if (A(i, l) >= A(j, l))
lower = l;
else
upper = l;
}
return lower;
}
int R(int i, int j) {
int lower = j - 1, upper = n;
while (upper - lower > 1) {
int r = (lower + upper) / 2;
if (B(i, r) >= B(j, r))
upper = r;
else
lower = r;
}
return upper;
}
int pp_[N], pp1[N], prank[N], qq_[N], qq1[N], qrank[N], ll_[N], rr_[N];
long long A_(int i, int l) {
return ll_[i] < l ? A(i, l) : A_(ll_[pp1[i]] >= l ? pp1[i] : pp_[i], l);
}
long long B_(int i, int r) {
return rr_[i] > r ? B(i, r) : B_(rr_[qq1[i]] <= r ? qq1[i] : qq_[i], r);
}
vl minimum_costs(vi aa_, vi ll, vi rr) {
int q = ll.size(), h, i, cnt;
vl ans(q);
n = aa_.size();
cnt = 0;
for (i = 0; i < n; i++) {
aa[i] = aa_[i];
while (cnt && aa[qu[cnt - 1]] < aa[i])
qq[qu[--cnt]] = i;
pp[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
while (cnt--)
qq[qu[cnt]] = n;
for (i = 0; i < n; i++)
dp[i] = (pp[i] == -1 ? 0 : dp[pp[i]]) + (long long) aa[i] * (i - pp[i]);
for (i = n - 1; i >= 0; i--)
dq[i] = (qq[i] == n ? 0 : dq[qq[i]]) + (long long) aa[i] * (qq[i] - i);
build(n);
cnt = 0, pp_[0] = ll_[0] = -1, pp1[0] = -1, prank[0] = -1, qu[cnt++] = 0;
for (i = 1; i < n; i++) {
while (cnt >= 2 && A(qu[cnt - 1], ll_[qu[cnt - 1]] + 1) > A(i, ll_[qu[cnt - 1]] + 1))
cnt--;
pp_[i] = qu[cnt - 1], ll_[i] = L(i, pp_[i]), qu[cnt++] = i;
if (pp1[pp_[i]] != -1 && prank[pp1[pp_[i]]] == prank[pp_[i]])
pp1[i] = pp1[pp1[pp_[i]]], prank[i] = prank[pp_[i]] + 1;
else
pp1[i] = pp_[i], prank[i] = 0;
}
cnt = 0, qq1[n - 1] = qq_[n - 1] = rr_[n - 1] = n, qq1[n - 1] = n, qrank[n - 1] = -1, qu[cnt++] = n - 1;
for (i = n - 2; i >= 0; i--) {
while (cnt >= 2 && B(qu[cnt - 1], rr_[qu[cnt - 1]] - 1) > B(i, rr_[qu[cnt - 1]] - 1))
cnt--;
qq_[i] = qu[cnt - 1], rr_[i] = R(i, qq_[i]), qu[cnt++] = i;
if (qq1[qq_[i]] != n && qrank[qq1[qq_[i]]] == qrank[qq_[i]])
qq1[i] = qq1[qq1[qq_[i]]], qrank[i] = qrank[qq_[i]] + 1;
else
qq1[i] = qq_[i], qrank[i] = 0;
}
for (h = 0; h < q; h++) {
int l = ll[h], r = rr[h], m = get(l, r);
ans[h] = (long long) aa[m] * (r - l + 1);
if (m > l)
ans[h] = min(ans[h], A_(m - 1, l) - ((qq[m] == n ? 0 : dq[qq[m]]) + (long long) aa[m] * (qq[m] - r - 1)));
if (m < r)
ans[h] = min(ans[h], B_(m + 1, r) - ((pp[m] == -1 ? 0 : dp[pp[m]]) + (long long) aa[m] * (l - pp[m] - 1)));
}
return ans;
}
Compilation message
meetings.cpp: In function 'void build(int)':
meetings.cpp:23:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
23 | ii[h][i] = ii[h - 1][(j = i + (1 << h - 1)) >= n || aa[ii[h - 1][i]] >= aa[ii[h - 1][j]] ? i : j];
| ~~^~~
meetings.cpp:25:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
25 | while (1 << h + 1 <= i)
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
3 ms |
972 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
972 KB |
Output is correct |
6 |
Correct |
4 ms |
972 KB |
Output is correct |
7 |
Correct |
3 ms |
972 KB |
Output is correct |
8 |
Correct |
3 ms |
972 KB |
Output is correct |
9 |
Correct |
3 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
3 ms |
972 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
972 KB |
Output is correct |
6 |
Correct |
4 ms |
972 KB |
Output is correct |
7 |
Correct |
3 ms |
972 KB |
Output is correct |
8 |
Correct |
3 ms |
972 KB |
Output is correct |
9 |
Correct |
3 ms |
972 KB |
Output is correct |
10 |
Correct |
8 ms |
1484 KB |
Output is correct |
11 |
Correct |
8 ms |
1416 KB |
Output is correct |
12 |
Correct |
8 ms |
1424 KB |
Output is correct |
13 |
Correct |
8 ms |
1484 KB |
Output is correct |
14 |
Correct |
8 ms |
1500 KB |
Output is correct |
15 |
Correct |
8 ms |
1484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
34 ms |
2900 KB |
Output is correct |
3 |
Correct |
205 ms |
17968 KB |
Output is correct |
4 |
Correct |
242 ms |
17788 KB |
Output is correct |
5 |
Correct |
183 ms |
17904 KB |
Output is correct |
6 |
Correct |
193 ms |
18000 KB |
Output is correct |
7 |
Correct |
237 ms |
18076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
34 ms |
2900 KB |
Output is correct |
3 |
Correct |
205 ms |
17968 KB |
Output is correct |
4 |
Correct |
242 ms |
17788 KB |
Output is correct |
5 |
Correct |
183 ms |
17904 KB |
Output is correct |
6 |
Correct |
193 ms |
18000 KB |
Output is correct |
7 |
Correct |
237 ms |
18076 KB |
Output is correct |
8 |
Correct |
214 ms |
17704 KB |
Output is correct |
9 |
Correct |
179 ms |
17784 KB |
Output is correct |
10 |
Correct |
233 ms |
17768 KB |
Output is correct |
11 |
Correct |
225 ms |
17684 KB |
Output is correct |
12 |
Correct |
176 ms |
17724 KB |
Output is correct |
13 |
Correct |
209 ms |
17712 KB |
Output is correct |
14 |
Correct |
221 ms |
17924 KB |
Output is correct |
15 |
Correct |
233 ms |
17736 KB |
Output is correct |
16 |
Correct |
231 ms |
17936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
3 |
Correct |
3 ms |
972 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
972 KB |
Output is correct |
6 |
Correct |
4 ms |
972 KB |
Output is correct |
7 |
Correct |
3 ms |
972 KB |
Output is correct |
8 |
Correct |
3 ms |
972 KB |
Output is correct |
9 |
Correct |
3 ms |
972 KB |
Output is correct |
10 |
Correct |
8 ms |
1484 KB |
Output is correct |
11 |
Correct |
8 ms |
1416 KB |
Output is correct |
12 |
Correct |
8 ms |
1424 KB |
Output is correct |
13 |
Correct |
8 ms |
1484 KB |
Output is correct |
14 |
Correct |
8 ms |
1500 KB |
Output is correct |
15 |
Correct |
8 ms |
1484 KB |
Output is correct |
16 |
Correct |
1 ms |
460 KB |
Output is correct |
17 |
Correct |
34 ms |
2900 KB |
Output is correct |
18 |
Correct |
205 ms |
17968 KB |
Output is correct |
19 |
Correct |
242 ms |
17788 KB |
Output is correct |
20 |
Correct |
183 ms |
17904 KB |
Output is correct |
21 |
Correct |
193 ms |
18000 KB |
Output is correct |
22 |
Correct |
237 ms |
18076 KB |
Output is correct |
23 |
Correct |
214 ms |
17704 KB |
Output is correct |
24 |
Correct |
179 ms |
17784 KB |
Output is correct |
25 |
Correct |
233 ms |
17768 KB |
Output is correct |
26 |
Correct |
225 ms |
17684 KB |
Output is correct |
27 |
Correct |
176 ms |
17724 KB |
Output is correct |
28 |
Correct |
209 ms |
17712 KB |
Output is correct |
29 |
Correct |
221 ms |
17924 KB |
Output is correct |
30 |
Correct |
233 ms |
17736 KB |
Output is correct |
31 |
Correct |
231 ms |
17936 KB |
Output is correct |
32 |
Correct |
1994 ms |
132492 KB |
Output is correct |
33 |
Correct |
1540 ms |
132636 KB |
Output is correct |
34 |
Correct |
2597 ms |
130368 KB |
Output is correct |
35 |
Correct |
2484 ms |
132396 KB |
Output is correct |
36 |
Correct |
1609 ms |
132616 KB |
Output is correct |
37 |
Correct |
2749 ms |
130376 KB |
Output is correct |
38 |
Correct |
2309 ms |
133888 KB |
Output is correct |
39 |
Correct |
3026 ms |
133884 KB |
Output is correct |
40 |
Correct |
2597 ms |
151232 KB |
Output is correct |
41 |
Correct |
1967 ms |
150124 KB |
Output is correct |
42 |
Correct |
2313 ms |
152180 KB |
Output is correct |
43 |
Correct |
2381 ms |
152232 KB |
Output is correct |
44 |
Correct |
2640 ms |
151392 KB |
Output is correct |