#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define t prev(s.end())
#define ff first
#define ss second
#define v vector
int n, q;
v<ll> helper(v<int32_t> h, v<int32_t> l, v<int32_t> r) {
v<v<pair<int, int>>> qq(n);
for (int i = 0; i < q; i++) qq[r[i]].push_back({ l[i], i });
v<ll> c(q);
ll curad = 0;
set <pair<int, pair<ll, ll>>> s;
v<pair<int, pair<ll, int>>> st;
v<v<int>> overtake(n + 1);
auto find_overtake = [&](pair<ll, ll> a, pair<ll, ll>b) -> int {
if (a.ff <= b.ff && a.ss <= b.ss) return 0;
if (b.ff <= a.ff && b.ss <= a.ss) return n;
int div = b.ss - a.ss;
return (int)min((ll)n, (a.ff - b.ff + (div - 1)) / div);
};
for (int i = 0; i < n; i++) {
while (st.size() && st.back().ss.ss < h[i]) st.pop_back();
if (st.size())curad = st.back().ss.ff + (ll)(i - st.back().ff) * h[i];
else curad = (ll)(i + 1) * h[i];
st.push_back({ i, {curad, h[i]} });
ll mn = curad - (ll)h[i] * i;int mni = i;
while (s.size() && t->ss.ss < h[i]) {
ll z = t->ss.ff + t->ss.ss * (i - 1) - (ll)h[i] * (i - 1);
if (z < mn) {
mn = z; mni = t->ff;
}
s.erase(t);
}
s.insert({ mni, {mn, h[i]} });
if (s.size() > 1) {
overtake[max(i, min(n, find_overtake(t->ss, prev(t)->ss)))].push_back(t->ff);
}
for (int k = 0; k < overtake[i].size(); k++) {
auto& x = overtake[i][k];
auto z = s.lower_bound({ x, {(ll)-1e18, (ll)-1e18} });
if (z == s.begin() || z == s.end() || z->ff != x) continue;
auto p = prev(z);
if (p->ss.ff + p->ss.ss * i < z->ss.ff + z->ss.ss * i) continue;
s.erase(p);
if (t == s.begin()) continue;
auto pp = prev(z);
overtake[max(i, min(n, find_overtake(z->ss, pp->ss)))].push_back(z->ff);
}
for (auto& x : qq[i]) {
c[x.ss] = 1e18;
int l = x.ff;
auto owo = lower_bound(st.begin(), st.end(), pair<int, pair<ll, int>>({ l, {(ll)-1e18, (int)-1e9 } }));
auto lll = s.lower_bound({ owo->ff, {(ll)-1e18, (ll)-1e18} });
if (lll == s.end()) continue;
c[x.ss] = lll->ss.ff + lll->ss.ss * i - owo->ss.ff + (ll)(owo->ff - l + 1) * owo->ss.ss;
}
}
return c;
}
v<ll> minimum_costs(v<int32_t> h, v<int32_t> l, v<int32_t> r) {
n = h.size(); q = l.size();
v<ll> a = helper(h, l, r);
reverse(h.begin(), h.end());
for (int i = 0; i < q; i++) { swap(l[i], r[i]); l[i] = n - 1 - l[i]; r[i] = n - 1 - r[i]; }
v<ll> b = helper(h, l, r);
v<ll> c(q); for (int i = 0; i < q;i++) c[i] = min(a[i], b[i]);
for (int i = 0; i < q; i++) {
if (c[i] == 1e18)
c[i] = (ll)(r[i] - l[i] + 1) * h[l[i]];
}
return c;
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> helper(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int k = 0; k < overtake[i].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
4 ms |
980 KB |
Output is correct |
11 |
Correct |
4 ms |
924 KB |
Output is correct |
12 |
Correct |
5 ms |
980 KB |
Output is correct |
13 |
Correct |
4 ms |
980 KB |
Output is correct |
14 |
Correct |
5 ms |
1108 KB |
Output is correct |
15 |
Correct |
4 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
26 ms |
3536 KB |
Output is correct |
3 |
Correct |
108 ms |
15792 KB |
Output is correct |
4 |
Correct |
84 ms |
15704 KB |
Output is correct |
5 |
Correct |
87 ms |
16972 KB |
Output is correct |
6 |
Correct |
82 ms |
18028 KB |
Output is correct |
7 |
Correct |
95 ms |
17436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
26 ms |
3536 KB |
Output is correct |
3 |
Correct |
108 ms |
15792 KB |
Output is correct |
4 |
Correct |
84 ms |
15704 KB |
Output is correct |
5 |
Correct |
87 ms |
16972 KB |
Output is correct |
6 |
Correct |
82 ms |
18028 KB |
Output is correct |
7 |
Correct |
95 ms |
17436 KB |
Output is correct |
8 |
Correct |
103 ms |
14420 KB |
Output is correct |
9 |
Correct |
83 ms |
13648 KB |
Output is correct |
10 |
Correct |
95 ms |
15568 KB |
Output is correct |
11 |
Correct |
98 ms |
14308 KB |
Output is correct |
12 |
Correct |
77 ms |
13476 KB |
Output is correct |
13 |
Correct |
94 ms |
15452 KB |
Output is correct |
14 |
Correct |
105 ms |
15484 KB |
Output is correct |
15 |
Correct |
86 ms |
14164 KB |
Output is correct |
16 |
Correct |
90 ms |
16540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
4 ms |
980 KB |
Output is correct |
11 |
Correct |
4 ms |
924 KB |
Output is correct |
12 |
Correct |
5 ms |
980 KB |
Output is correct |
13 |
Correct |
4 ms |
980 KB |
Output is correct |
14 |
Correct |
5 ms |
1108 KB |
Output is correct |
15 |
Correct |
4 ms |
1108 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
26 ms |
3536 KB |
Output is correct |
18 |
Correct |
108 ms |
15792 KB |
Output is correct |
19 |
Correct |
84 ms |
15704 KB |
Output is correct |
20 |
Correct |
87 ms |
16972 KB |
Output is correct |
21 |
Correct |
82 ms |
18028 KB |
Output is correct |
22 |
Correct |
95 ms |
17436 KB |
Output is correct |
23 |
Correct |
103 ms |
14420 KB |
Output is correct |
24 |
Correct |
83 ms |
13648 KB |
Output is correct |
25 |
Correct |
95 ms |
15568 KB |
Output is correct |
26 |
Correct |
98 ms |
14308 KB |
Output is correct |
27 |
Correct |
77 ms |
13476 KB |
Output is correct |
28 |
Correct |
94 ms |
15452 KB |
Output is correct |
29 |
Correct |
105 ms |
15484 KB |
Output is correct |
30 |
Correct |
86 ms |
14164 KB |
Output is correct |
31 |
Correct |
90 ms |
16540 KB |
Output is correct |
32 |
Correct |
953 ms |
105640 KB |
Output is correct |
33 |
Correct |
618 ms |
99496 KB |
Output is correct |
34 |
Correct |
1171 ms |
114372 KB |
Output is correct |
35 |
Correct |
1037 ms |
105748 KB |
Output is correct |
36 |
Correct |
667 ms |
99700 KB |
Output is correct |
37 |
Correct |
1186 ms |
114296 KB |
Output is correct |
38 |
Correct |
1181 ms |
115380 KB |
Output is correct |
39 |
Correct |
1766 ms |
135672 KB |
Output is correct |
40 |
Correct |
1096 ms |
114128 KB |
Output is correct |
41 |
Correct |
888 ms |
111220 KB |
Output is correct |
42 |
Correct |
965 ms |
111788 KB |
Output is correct |
43 |
Correct |
964 ms |
111672 KB |
Output is correct |
44 |
Correct |
1048 ms |
104880 KB |
Output is correct |