#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
vt<ll> Sub2(vt<int> H, vt<int> L, vt<int> R) {
const int N = size(H), Q = size(L);
vt<ll> ans(Q, LLONG_MAX);
ll fdp[N], rdp[N];
FOR(q, 0, Q-1) {
int l = L[q], r = R[q];
vt<int> sk;
FOR(i, l, r) {
while (size(sk) && H[sk.back()] <= H[i])
sk.pop_back();
fdp[i] = (size(sk) ? fdp[sk.back()] : 0ll) + 1ll * H[i] * (i - (size(sk) ? sk.back() : l-1));
sk.push_back(i);
}
sk.clear();
ROF(i, r, l) {
while (size(sk) && H[sk.back()] <= H[i])
sk.pop_back();
rdp[i] = (size(sk) ? rdp[sk.back()] : 0ll) + 1ll * H[i] * ((size(sk) ? sk.back() : r+1) - i);
ans[q] = min(ans[q], rdp[i] + fdp[i] - H[i]);
sk.push_back(i);
}
}
return ans;
}
struct ST {
struct Node {
int ans, p, s, len;
};
vt<Node> st;
ST(vt<int> &A) {
st.resize(size(A) << 2);
build(A);
}
Node merge(Node a, Node b) {
return {max({a.ans, b.ans, a.s + b.p}), a.p + (a.p == a.len) * b.p, b.s + (b.s == b.len) * a.s, a.len + b.len};
}
#define lc i << 1
#define rc i << 1 | 1
void build(vt<int> &A, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st) >> 2;
if (tl == tr)
st[i] = {A[tl] < 2, A[tl] < 2, A[tl] < 2, 1};
else {
int tm = tl + tr >> 1;
build(A, lc, tl, tm);
build(A, rc, tm+1, tr);
st[i] = merge(st[lc], st[rc]);
}
}
Node qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0)
tr += size(st) >> 2;
if (ql <= tl && tr <= qr)
return st[i];
if (tl > qr || tr < ql)
return {0, 0, 0, 0};
int tm = tl + tr >> 1;
return merge(qry(ql, qr, lc, tl, tm), qry(ql, qr, rc, tm+1, tr));
}
#undef lc
#undef rc
};
vt<ll> Sub3(vt<int> H, vt<int> L, vt<int> R) {
const int Q = size(L);
ST st(H);
vt<ll> ans(Q);
FOR(i, 0, Q-1) {
int l = L[i], r = R[i];
int v = st.qry(l, r).ans;
ans[i] = v + 2 * (r - l + 1 - v);
}
return ans;
}
vt<ll> minimum_costs(vt<int> H, vt<int> L, vt<int> R) {
const int N = size(H), Q = size(L);
if (N <= 5000 && Q <= 5000)
return Sub2(H, L, R);
if (*max_element(all(H)) < 3)
return Sub3(H, L, R);
}
Compilation message
meetings.cpp: In member function 'void ST::build(std::vector<int>&, int, int, int)':
meetings.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int tm = tl + tr >> 1;
| ~~~^~~~
meetings.cpp: In member function 'ST::Node ST::qry(int, int, int, int, int)':
meetings.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int tm = tl + tr >> 1;
| ~~~^~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
98 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
476 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
476 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
128 ms |
804 KB |
Output is correct |
11 |
Correct |
482 ms |
804 KB |
Output is correct |
12 |
Correct |
126 ms |
812 KB |
Output is correct |
13 |
Correct |
536 ms |
852 KB |
Output is correct |
14 |
Correct |
55 ms |
856 KB |
Output is correct |
15 |
Correct |
63 ms |
808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
24 ms |
2908 KB |
Output is correct |
3 |
Correct |
77 ms |
13140 KB |
Output is correct |
4 |
Correct |
79 ms |
13000 KB |
Output is correct |
5 |
Correct |
50 ms |
12884 KB |
Output is correct |
6 |
Correct |
61 ms |
12884 KB |
Output is correct |
7 |
Correct |
80 ms |
12880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
24 ms |
2908 KB |
Output is correct |
3 |
Correct |
77 ms |
13140 KB |
Output is correct |
4 |
Correct |
79 ms |
13000 KB |
Output is correct |
5 |
Correct |
50 ms |
12884 KB |
Output is correct |
6 |
Correct |
61 ms |
12884 KB |
Output is correct |
7 |
Correct |
80 ms |
12880 KB |
Output is correct |
8 |
Incorrect |
66 ms |
12844 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
476 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
128 ms |
804 KB |
Output is correct |
11 |
Correct |
482 ms |
804 KB |
Output is correct |
12 |
Correct |
126 ms |
812 KB |
Output is correct |
13 |
Correct |
536 ms |
852 KB |
Output is correct |
14 |
Correct |
55 ms |
856 KB |
Output is correct |
15 |
Correct |
63 ms |
808 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
24 ms |
2908 KB |
Output is correct |
18 |
Correct |
77 ms |
13140 KB |
Output is correct |
19 |
Correct |
79 ms |
13000 KB |
Output is correct |
20 |
Correct |
50 ms |
12884 KB |
Output is correct |
21 |
Correct |
61 ms |
12884 KB |
Output is correct |
22 |
Correct |
80 ms |
12880 KB |
Output is correct |
23 |
Incorrect |
66 ms |
12844 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |