#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
#define a first
#define b second
#define pb push_back
#define all(a) (a).begin(), (a).end()
constexpr int maxn = 2e5+10;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
static const ll inf = 0x3f3f3f3f3f3f3f3f;
ll div(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
if(empty()) return 0ll;
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
struct SegmentTree
{
LineContainer tree[4*maxn];
void upd(int node, int i, int j, int l, int r, const pii& L) {
if(i > r || j < l) return;
if(i >= l && j <= r) return (void)(tree[node].add(L.a, L.b));
int m = (i+j) >> 1;
upd(node<<1, i, m, l, r, L);
upd(node<<1|1, m+1, j, l, r, L);
}
ll query(int node, int i, int j, int pos, ll x) {
if(i == j) return tree[node].query(x);
int m = (i+j) >> 1;
if(pos <= m) return max(tree[node].query(x), query(node<<1, i, m, pos, x));
return max(tree[node].query(x), query(node<<1|1, m+1, j, pos, x));
}
void clear() { for(int i = 0; i < 4*maxn; i++) tree[i].clear(); }
} seg;
struct SegmentTreeNormal
{
ll tree[4*maxn];
void upd(int node, int i, int j, int pos, ll v, bool set = 0) {
if(i == j) return (void)(tree[node] = set?v:max(tree[node], v));
int m = (i+j) >> 1;
if(pos <= m) upd(node<<1, i, m, pos, v, set);
else upd(node<<1|1, m+1, j, pos, v, set);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
ll query(int node, int i, int j, int l, int r) {
if(i > r || j < l) return 0;
if(i >= l && j <= r) return tree[node];
int m = (i+j) >> 1;
ll ans = query(node<<1, i, m, l, r);
ans = max(ans, query(node<<1|1, m+1, j, l, r));
return ans;
}
void clear() { memset(tree, 0, sizeof tree); }
} seg2, seg3;
struct Query
{
int l, r;
} queries[maxn], itv[maxn];
struct Event
{
int t, x, id;
bool operator<(Event e) {
if(x == e.x) return t < e.t;
return x < e.x;
}
};
vector<Event> events;
int a[maxn];
ll soma[maxn], suf[maxn];
multiset<int> ativos[maxn];
ll sum(int l, int r) { return soma[r] - soma[l-1]; }
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = (int)H.size(), q = (int)L.size();
vector<ll> ans(q);
for(int i = 0; i < n; i++)
a[i+1] = -H[i];
for(int i = 1; i <= n; i++)
soma[i] = soma[i-1] + a[i];
for(int i = n; i >= 1; i--)
suf[i] = suf[i+1] + a[i];
stack<int> st;
for(int i = 1; i <= n; i++) {
while(st.size() && a[i] <= a[st.top()]) {
int id = st.top();
st.pop();
itv[id] = {st.size()?st.top()+1:1, i-1};
events.pb({-1, st.size()?st.top()+1:1, id});
events.pb({1, i-1, id});
}
st.push(i);
}
while(st.size()) {
int id = st.top();
st.pop();
itv[id] = {st.size()?st.top()+1:1, n};
events.pb({-1, st.size()?st.top()+1:1, id});
events.pb({1, n, id});
}
for(int i = 0; i < q; i++) {
queries[i].l = L[i], queries[i].r = R[i];
events.pb({2, queries[i].r, i});
}
sort(all(events));
for(auto& e : events) {
auto [t, r, id] = e;
if(t == -1) {
int l = itv[id].l;
ativos[l].insert(a[id]);
seg3.upd(1, 1, n, l, *ativos[l].rbegin(), 1);
}
if(t == 1) {
int l = itv[id].l;
ativos[l].erase(ativos[l].find(a[id]));
seg3.upd(1, 1, n, l, ativos[l].size()?*ativos[l].rbegin():0, 1);
pii reta = {-a[id], a[id] * soma[r]};
seg.upd(1, 1, n, l, r, reta);
seg2.upd(1, 1, n, l, 1ll*a[id]*sum(l, r));
e.x = -l + n + 1;
}
if(t == 2) {
int l = queries[id].l;
ans[id] = max(ans[id], seg.query(1, 1, n, l, soma[l-1]));
ans[id] = max(ans[id], seg2.query(1, 1, n, l, r));
ans[id] = max(ans[id], seg3.query(1, 1, n, 1, l) * sum(l, r));
e.x = -l + n + 1;
}
}
seg.clear();
seg2.clear();
sort(all(events));
for(auto& e : events) {
auto [t, r, id] = e;
if(t == 1) {
int l = n+1 - itv[id].r;
pii reta = {-a[id], a[id] * suf[n+1-r]};
seg.upd(1, 1, n, l, r, reta);
e.x = itv[id].r;
}
if(t == 2) {
int l = n+1 - queries[id].r;
ans[id] = max(ans[id], seg.query(1, 1, n, l, suf[n+1-(l-1)]));
e.x = itv[id].r;
}
}
// for(int i = 0; i < q; i++)
// printf("%lld\n", ans[i]);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
40 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
40 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
53612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
