#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct func {
int a;
ll b, c;
func() {
a = 1, b = c = 0;
}
func(int aa, ll bb, ll cc) : a(aa), b(bb), c(cc) {}
// this * x
func operator * (const func &x) const {
return func(a * x.a, a * x.b + b, a * x.c + c);
}
// x * this
void operator *= (const func &x) {
a = x.a * a;
b = x.a * b + x.b;
c = x.a * c + x.c;
}
ll operator () (ll x, int i) const {
return a * x + b * i + c;
}
};
struct segtree {
int n;
vector<ll> t;
vector<int> ind;
vector<func> tag;
segtree() {}
segtree(int sz) {
init(sz);
}
void init(int sz) {
n = max(2, sz);
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n, 0);
tag.resize(2 * n, func());
ind.resize(2 * n);
for (int i = 0; i < n; i++)
ind[i + n - 1] = i;
for (int i = n - 2; i >= 0; i--)
ind[i] = ind[2 * i + 1];
}
void clear() {
for (auto &i : t) i = 0;
for (auto &i : tag) i = func();
}
void push(int x) {
t[x] = tag[x](t[x], ind[x]);
if (x < n - 1) {
tag[2 * x + 1] *= tag[x];
tag[2 * x + 2] *= tag[x];
}
tag[x] = func();
}
// assumes x has no tag
void fix(int x) {
push(2 * x + 1);
t[x] = t[2 * x + 1];
}
// a[i] = x
void set(ll x, int i) {
func f(0, 0, x);
upd(i, i, f, 0, 0, n - 1);
}
// for each i in [l, r], add st + d * (i - l)
void progress(int l, int r, ll st, ll d) {
func f(1, d, st - d * l);
upd(l, r, f, 0, 0, n - 1);
}
// for each i in monotonic [l, r], set a[i] = min(a[i], x)
void minimize(int l, int r, ll x) {
int m = last(l, r, x);
if (m != -1) {
func f(0, 0, x);
upd(l, m, f, 0, 0, n - 1);
}
}
void upd(int l, int r, const func &f, int node, int nl, int nr) {
if (r < nl || nr < l) return;
if (l <= nl && nr <= r) {
tag[node] *= f;
return;
}
push(node);
int mid = (nl + nr) / 2;
upd(l, r, f, 2 * node + 1, nl, mid);
upd(l, r, f, 2 * node + 2, mid + 1, nr);
fix(node);
}
// smallest i in [l, r] s.t a[i] >= x
int last(int l, int r, ll x) {
return last(l, r, x, 0, 0, n - 1);
}
int last(int l, int r, ll x, int node, int nl, int nr) {
if (r < nl || nr < l) return -1;
push(node);
if (l <= nl && nr <= r && t[node] < x) return -1;
if (nl == nr) return nl;
int mid = (nl + nr) / 2, tmp;
tmp = last(l, r, x, 2 * node + 2, mid + 1, nr);
if (tmp != -1) return tmp;
return last(l, r, x, 2 * node + 1, nl, mid);
}
ll operator [] (int i) const {
int org = i;
i += n - 1;
ll rtn = t[i];
rtn = tag[i](rtn, org);
i = (i - 1) / 2;
while (i) {
rtn = tag[i](rtn, org);
i = (i - 1) / 2;
}
rtn = tag[0](rtn, org);
return rtn;
}
};
struct mtree {
int n;
const ll b = 1 << 30;
vector<ll> t;
mtree() {}
mtree(const vector<int> &a) {
init(a);
}
void init(const vector<int> &a) {
n = max(2, (int)a.size());
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n);
for (int i = 0; i < a.size(); i++)
t[i + n - 1] = b * a[i] + i;
for (int i = n - 2; i >= 0; i--)
t[i] = max(t[2 * i + 1], t[2 * i + 2]);
}
int query(int l, int r) const {
ll mx = -1;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) mx = max(mx, t[l++]);
if (r & 1) mx = max(mx, t[r--]);
}
if (l == r) mx = max(mx, t[l]);
return mx % b;
}
ll vquery(int l, int r) const {
ll mx = -1;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) mx = max(mx, t[l++]);
if (r & 1) mx = max(mx, t[r--]);
}
if (l == r) mx = max(mx, t[l]);
return mx / b;
}
};
struct query {
int l, r, i;
query() {}
query(int ll, int rr, int ii) : l(ll), r(rr), i(ii) {}
};
const int mxn = 750005;
int n;
vector<int> a;
int S[mxn], E[mxn], L[mxn], R[mxn], root;
vector<query> Q[mxn];
vector<ll> ans;
mtree M;
segtree T;
int preprocess(int l, int r) {
if (l > r) return -1;
int v = M.query(l, r);
if (OO) {
cout << "preprocessing in [" << l << ", " << r << "], v = " << v << '\n';
}
S[v] = l;
E[v] = r;
L[v] = preprocess(l, v - 1);
R[v] = preprocess(v + 1, r);
return v;
}
void preprocess(const vector<int> &l, const vector<int> &r) {
M.init(a);
T.init(n);
root = preprocess(0, n - 1);
for (int i = 0; i < ans.size(); i++) {
ans[i] = ll(r[i] - l[i] + 1) * M.vquery(l[i], r[i]);
int v = M.query(l[i], r[i]);
if (OO) {
cout << "attaching query " << l[i] << " " << r[i] << " to " << v << '\n';
}
Q[v].push_back(query(l[i], r[i], i));
}
}
void solve(int v, int prev) {
if (v < 0 || n <= v) return;
solve(L[v], v);
solve(R[v], v);
if (OO) cout << "solving " << v << " " << prev << '\n';
if (OO) {
cout << "before:\n";
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
}
if (S[v] == v) T.set(a[v], v);
else T.set(T[v - 1] + a[v], v);
if (v < E[v]) {
ll c = (v > 0 ? T[v - 1] : 0) + a[v] * (1 - (v - S[v]));
T.progress(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0);
T.progress(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]);
T.minimize(v + 1, E[v], c);
T.progress(v + 1, E[v], ll(v - S[v] + 1) * a[v], a[v]);
}
if (OO) {
cout << "after:\n";
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
}
if (prev != -1 && prev < v) {
for (const auto &i : Q[prev]) {
if (prev < i.r) {
if (OO) cout << "updating query " << i.l << " " << i.r << '\n';
ans[i.i] = min(ans[i.i], ll(prev - i.l + 1) * a[prev] + T[i.r]);
}
}
}
}
vector<ll> minimum_costs(vector<int> H, vector<int> l,
vector<int> r) {
n = H.size();
a = H;
ans.resize(l.size());
preprocess(l, r);
if (OO) {
cout << "preprocessed\n";
cout << "L: ";
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
cout << "R: ";
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
cout << "S: ";
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
cout << "E: ";
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
}
solve(root, -1);
// reverse
reverse(a.begin(), a.end());
auto flip = [](int &x, int y) {
x = y - 1 - x;
};
for (int i = 0; i < n; i++) {
flip(S[i], n);
flip(E[i], n);
swap(S[i], E[i]);
flip(L[i], n);
flip(R[i], n);
swap(L[i], R[i]);
}
for (int i = 0; i < n; i++) {
for (auto &j : Q[i]) {
flip(j.l, n);
flip(j.r, n);
swap(j.l, j.r);
}
}
reverse(Q, Q + n);
reverse(S, S + n);
reverse(E, E + n);
reverse(L, L + n);
reverse(R, R + n);
M.init(a);
T.clear();
flip(root, n);
if (OO) {
cout << "reversed\n";
cout << "L: ";
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
cout << "R: ";
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
cout << "S: ";
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
cout << "E: ";
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
cout << '\n';
cout << "current answers: ";
for (const auto &i : ans) cout << i << " "; cout << '\n';
}
solve(root, -1);
return ans;
}
Compilation message
meetings.cpp: In member function 'void mtree::init(const std::vector<int>&)':
meetings.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++)
~~^~~~~~~~~~
meetings.cpp: In function 'void preprocess(const std::vector<int>&, const std::vector<int>&)':
meetings.cpp:201:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++) {
~~^~~~~~~~~~~~
meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:218:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
^~~
meetings.cpp:218:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
^~~~
meetings.cpp:232:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
^~~
meetings.cpp:232:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
^~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:255:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
^~~
meetings.cpp:255:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
^~~~
meetings.cpp:257:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
^~~
meetings.cpp:257:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
^~~~
meetings.cpp:259:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
^~~
meetings.cpp:259:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
^~~~
meetings.cpp:261:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
^~~
meetings.cpp:261:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
^~~~
meetings.cpp:295:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
^~~
meetings.cpp:295:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
^~~~
meetings.cpp:297:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
^~~
meetings.cpp:297:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
^~~~
meetings.cpp:299:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
^~~
meetings.cpp:299:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
^~~~
meetings.cpp:301:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
^~~
meetings.cpp:301:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
^~~~
meetings.cpp:304:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : ans) cout << i << " "; cout << '\n';
^~~
meetings.cpp:304:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : ans) cout << i << " "; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
18044 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
18424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
18044 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
18424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
17884 KB |
Output is correct |
| 2 |
Correct |
97 ms |
22056 KB |
Output is correct |
| 3 |
Correct |
636 ms |
44988 KB |
Output is correct |
| 4 |
Correct |
611 ms |
36988 KB |
Output is correct |
| 5 |
Correct |
570 ms |
46144 KB |
Output is correct |
| 6 |
Correct |
627 ms |
46932 KB |
Output is correct |
| 7 |
Correct |
712 ms |
48916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
17884 KB |
Output is correct |
| 2 |
Correct |
97 ms |
22056 KB |
Output is correct |
| 3 |
Correct |
636 ms |
44988 KB |
Output is correct |
| 4 |
Correct |
611 ms |
36988 KB |
Output is correct |
| 5 |
Correct |
570 ms |
46144 KB |
Output is correct |
| 6 |
Correct |
627 ms |
46932 KB |
Output is correct |
| 7 |
Correct |
712 ms |
48916 KB |
Output is correct |
| 8 |
Correct |
542 ms |
37700 KB |
Output is correct |
| 9 |
Correct |
498 ms |
37408 KB |
Output is correct |
| 10 |
Correct |
518 ms |
37812 KB |
Output is correct |
| 11 |
Correct |
521 ms |
36920 KB |
Output is correct |
| 12 |
Correct |
500 ms |
36660 KB |
Output is correct |
| 13 |
Correct |
505 ms |
37196 KB |
Output is correct |
| 14 |
Correct |
630 ms |
45032 KB |
Output is correct |
| 15 |
Correct |
512 ms |
36708 KB |
Output is correct |
| 16 |
Correct |
691 ms |
45232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
18044 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
18424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
