#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 750'000 + 10;
int pre[N], nxt[N], lg[N], sp[20][N];
long long h[N];
vector<int> query[N];
struct IT {
pair<long long, long long> lazy[N << 2];
void gather(pair<long long, long long> &a, pair<long long, long long> &b) {
if (b.first != -1e9) a = b;
else a.second += b.second;
}
void push(int s, int l, int r) {
if (l == r) return;
gather(lazy[s << 1], lazy[s]);
gather(lazy[s << 1 | 1], lazy[s]);
lazy[s] = make_pair(-1e9, 0);
}
void up(int s, int l, int r, int from, int to, pair<long long, long long> val) {
push(s, l, r);
if (l > to || r < from) return;
if (from <= l && r <= to) {
gather(lazy[s], val);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
}
pair<long long, long long> get(int s, int l, int r, int pos) {
push(s, l, r);
if (l == r) return lazy[s];
int mid = l + r >> 1;
if (pos <= mid) return get(s << 1, l, mid, pos);
return get(s << 1 | 1, mid + 1, r, pos);
}
} prefix, suffix;
int best(int x, int y) {
if (h[x] == h[y]) return x < y ? x : y;
return h[x] > h[y] ? x : y;
}
int getmax (int l, int r) {
int k = lg[r - l + 1];
return best(sp[k][l], sp[k][r - (1 << k) + 1]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int q = L.size();
int n = H.size();
for(int i = 0; i < n; i++) sp[0][i] = i, h[i] = H[i];
for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) {
sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
}
vector<long long> ans(q);
for(int i = 0; i < q; i++) {
ans[i] = 1e18;
if (L[i] == R[i]) ans[i] = h[i];
else {
int x = getmax(L[i], R[i]);
query[x].emplace_back(i);
}
}
vector<int> order(n);
for(int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [] (const int &x, const int &y) {
if (h[x] == h[y]) return x > y;
return h[x] < h[y];
});
for(int i = 1; i <= 4 * n; i++) prefix.lazy[i] = suffix.lazy[i] = make_pair(-1e9, 0);
auto get_prefix = [&] (int pos) {
pair<long long, long long> tmp = prefix.get(1, 0, n - 1, pos);
if (tmp.first == -1e9) return tmp.second;
return tmp.first * pos + tmp.second;
};
auto get_suffix = [&] (int pos) {
pair<long long, long long> tmp = suffix.get(1, 0, n - 1, pos);
if (tmp.first == -1e9) return tmp.second;
return tmp.first * pos + tmp.second;
};
for(int i = 0; i < n; i++) pre[i] = i - 1, nxt[i] = i + 1;
for(int cur = 0; cur < n; cur++) {
int v = order[cur];
int from = pre[v], to = nxt[v];
if (from > 0) nxt[from] = to;
if (to < n) pre[to] = from;
from++; to--;
prefix.up(1, 0, n - 1, v, v, make_pair(0, get_prefix(v - 1) + h[v]));
suffix.up(1, 0, n - 1, v, v, make_pair(0, get_suffix(v + 1) + h[v]));
for(int &j : query[v]) {
if (j == 0) {
// cout << get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v] << endl;
}
if (L[j] != v) ans[j] = min(ans[j], get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v]);
if (R[j] != v) ans[j] = min(ans[j], get_prefix(R[j]) + 1LL * (v - L[j] + 1) * h[v]);
}
long long left = get_prefix(v - 1);
long long right = get_prefix(v + 1);
// cout << from << " " << to << " " << v << endl;
// cout << left << " " << right << endl;
// cout << endl;
int l, r, last;
l = v + 1, r = from, last = v;
while (l <= r) {
int mid = l + r >> 1;
if (left + h[v] * (mid - v + 1) <= h[v] * (v - from + 1) + get_prefix(mid)) {
last = mid;
l = mid + 1;
} else r = mid - 1;
}
if (v + 1 <= last) prefix.up(1, 0, n - 1, v + 1, last, make_pair(h[v], left - h[v] * (v - 1)));
if (last + 1 <= to) prefix.up(1, 0, n - 1, last + 1, to, make_pair(-1e9, h[v] * (v - from + 1)));
l = from, r = v - 1, last = v;
while (l <= r) {
int mid = l + r >> 1;
if (right + h[v] * (v - mid + 1) <= h[v] * (to - v + 1) + get_suffix(mid)) {
last = mid;
r = mid - 1;
} else l = mid + 1;
}
if (last <= v - 1) suffix.up(1, 0, n - 1, last, v - 1, make_pair(-h[v], right + h[v] * (v + 1)));
if (from <= last - 1) suffix.up(1, 0, n - 1, from, last - 1, make_pair(-1e9, h[v] * (to - v + 1)));
// if (v == 0) {
//// prefix.up(1, 0, n - 1, 0, 0, make_pair(0, 2));
// cout << get_suffix(0) << endl;
// }
}
return ans;
}
#ifdef ngu
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}
#endif // ngu
Compilation message
meetings.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<long long int, long long int>)':
meetings.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l + r >> 1;
| ~~^~~
meetings.cpp: In member function 'std::pair<long long int, long long int> IT::get(int, int, int, int)':
meetings.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
69 | sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
| ~~^~~
meetings.cpp:139:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
139 | int mid = l + r >> 1;
| ~~^~~
meetings.cpp:152:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
152 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
29016 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
54048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
29016 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
54048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29020 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
60372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29020 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
60372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
29016 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
54048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
