이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 750005;
const ll oo = 1e18;
int n, q;
pi st[N][20];
int argmax(int L, int R) { // [L, R]
int k = __lg(R - L + 1);
return max(st[L][k], st[R - (1 << k) + 1][k]).S;
};
ll ans[N];
vi G[N];
struct node {
ll l_val, r_val;
ll m, b;
ll lz;
int tl, tr;
node(ll val = 0) {
l_val = r_val = val;
m = b = lz = 0;
}
} t[N * 4];
void pull(int v) {
t[v].l_val = t[v * 2].l_val;
t[v].r_val = t[v * 2].r_val;
}
void apply_add(int v, ll x) {
t[v].l_val += x, t[v].r_val += x;
if(t[v].m) {
t[v].b += x;
} else {
t[v].lz += x;
}
}
void apply_set(int v, ll m, ll b) {
t[v].l_val = t[v].tl * m + b;
t[v].r_val = (t[v].tr - 1) * m + b;
t[v].m = m, t[v].b = b;
t[v].lz = 0;
}
void push(int v) {
if(t[v].m) { // set
apply_set(v * 2, t[v].m, t[v].b);
apply_set(v * 2 + 1, t[v].m, t[v].b);
t[v].m = t[v].b = 0;
} else { // add
apply_add(v * 2, t[v].lz);
apply_add(v * 2 + 1, t[v].lz);
t[v].lz = 0;
}
}
void build(int v = 1, int tl = 0, int tr = n) {
t[v] = node();
t[v].tl = tl, t[v].tr = tr;
if(tr - tl == 1)
return;
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
}
void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
apply_add(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
pull(v);
}
ll qry(int pos, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1)
return t[v].l_val;
push(v);
int tm = (tl + tr) / 2;
if(pos < tm) return qry(pos, v * 2, tl, tm);
else return qry(pos, v * 2 + 1, tm, tr);
}
void cmin(int l, int r, ll m, ll b, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
if(t[v].r_val >= m * (tr - 1) + b) {
apply_set(v, m, b);
return;
}
if(t[v].l_val <= m * tl + b)
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) cmin(l, r, m, b, v * 2, tl, tm);
if(r > tm) cmin(l, r, m, b, v * 2 + 1, tm, tr);
pull(v);
}
int h[N], l[N], r[N];
void dfs(int L, int R) { // [L, R]
if(L > R) return;
int m = argmax(L, R);
dfs(L, m - 1), dfs(m + 1, R);
for(int i:G[m]) {
ll cur = 1LL * (m - l[i] + 1) * h[m];
if(r[i] > m) cur += qry(r[i]);
ans[i] = min(ans[i], cur);
}
assert(qry(m) == 0);
add(m, R + 1, 1LL * (m - L + 1) * h[m]);
if(L < m)
cmin(m, R + 1, h[m], qry(m - 1) - h[m] * (m - 1));
}
void solve() {
for(int i = 0; i < n; i++)
st[i][0] = {h[i], i};
for(int j = 1; j < 20; j++)
for(int i = 0; i + (1 << j) - 1 < n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for(int i = 0; i < q; i++)
G[argmax(l[i], r[i])].PB(i);
build();
dfs(0, n - 1);
for(int i = 0; i < n; i++)
G[i].clear();
}
V<ll> minimum_costs(vi _h, vi _l, vi _r) {
n = SZ(_h), q = SZ(_l);
for(int i = 0; i < n; i++) h[i] = _h[i];
for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i], ans[i] = oo;
solve();
reverse(h, h + n);
for(int i = 0; i < q; i++) {
swap(l[i], r[i]);
l[i] = n - l[i] - 1, r[i] = n - r[i] - 1;
}
solve();
V<ll> tt;
for(int i = 0; i < q; i++)
tt.PB(ans[i]);
return tt;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |