| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 238810 | Jatana | Meetings (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "meetings.h"
#include <algorithm>
#include <cassert>
#define le(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define f(i, n) for (int i = 0; i < (n); i++)
#define x first
#define y second
using namespace std;
typedef long long ll;
struct F {
ll c = 0, a = 0, b = 0;
};
const ll INF = 1e18;
const F eye{0, 0, (ll)INF};
bool operator==(const F &a, const F &b) {
return a.c == b.c && a.a == b.a && a.b == b.b;
}
typedef pair<ll, ll> line;
ll eval(line l, ll x) {
return l.x * x + l.y;
}
ll eval(F func, ll x, ll y) {
return min(x + func.c, 1LL * func.a * y + func.b);
}
struct TS {
vector<F> func;
int n;
TS() {}
TS(int _n) {
n = _n;
func.resize(2 * n, eye);
}
ll get(int i, int tl, int tr, int j) {
if (tl + 1 == tr) return eval(func[i], 0, j);
int m = (tl + tr) / 2;
if (j < m) {
return eval(func[i], get(i + 1, tl, m, j), j);
} else return eval(func[i], get(i + (m - tl) * 2, m, tr, j), j);
}
ll get(int j) {
return get(0, 0, n, j);
}
void act(int i, int tl, int tr, F h) {
if (func[i] == eye) {
func[i] = h;
return;
}
line l1 = mp(func[i].a, func[i].b + h.c);
line l2 = mp(h.a, h.b);
func[i].c += h.c;
l1.y -= func[i].c; l2.y -= func[i].c;
int m = (tl + tr) / 2;
if (eval(l1, m) > eval(l2, m))
swap(l1, l2);
func[i].a = l1.x; func[i].b = l1.y;
func[i].b += func[i].c;
if (tl + 1 != tr) {
if (eval(l2, tl) < eval(l1, tl)) {
act(i + 1, tl, m, {0, l2.x, l2.y});
} else
act(i + (m - tl) * 2, m, tr, {0, l2.x, l2.y});
}
}
void app(int i, int tl, int tr, int ql, int qr, F h) {
if (tr <= ql || qr <= tl) return;
if (ql <= tl && tr <= qr) {
act(i, tl, tr, h);
} else {
int m = (tl + tr) / 2;
// assert(func[i] == eye);
app(i + 1, tl, m, ql, qr, h);
app(i + (m - tl) * 2, m, tr, ql, qr, h);
}
}
};
vector<int> H;
vector<int> mx[21];
#include <numeric>
int query(int l, int r) {
int p = 31 - __builtin_clz(r - l);
int a = mx[p][l];
int b = mx[p][r - (1 << p)];
if (H[a] >= H[b]) return a;
return b;
}
void init() {
mx[0] = vector<int>(le(H), 0);
iota(mx[0].begin(), mx[0].end(), 0);
for (int i = 1; i < 21; i++) {
mx[i] = mx[i - 1];
for (int j = 0; j < le(H); j++) {
int sub = j + (1 << (i - 1));
if (sub < le(H)) {
if (H[mx[i - 1][sub]] > H[mx[i][j]]) {
mx[i][j] = mx[i - 1][sub];
}
}
}
}
}
vector<ll> dp[2];
TS sp[2];
vector<int> L;
vector<int> R;
vector<ll> rez;
vector<vector<int>> qs;
void process(int l, int r, int m) {
for (int id : qs[m]) {
// either left or right
rez[id] = min(
sp[0].get(0, 0, sp[0].n, R[id]) + 1LL * H[m] * (m - L[id] + 1),
sp[1].get(0, 0, sp[1].n, L[id]) + 1LL * H[m] * (R[id] - m + 1)
);
}
dp[0][m] = (m - 1 >= l ? sp[0].get(m - 1) : 0) + H[m];
sp[0].app(0, 0, sp[0].n, m, m + 1, {dp[0][m], 0, (ll)INF});
sp[0].app(0, 0, sp[0].n, m + 1, r, {
1LL * (m - l + 1) * H[m],
H[m],
dp[0][m] - 1LL * m * H[m]
});
// for (int i = m + 1; i < r; i++) {
// dp[0][i] = min(
// dp[0][i] + 1LL * (m - l + 1) * H[m],
// dp[0][m] + 1LL * (i - m) * H[m]
// );
// }
dp[1][m] = (m + 1 < r ? sp[1].get(m + 1) : 0) + H[m];
sp[1].app(0, 0, sp[1].n, m, m + 1, {dp[1][m], 0, (ll)INF});
sp[1].app(0, 0, sp[1].n, l, m, {
1LL * (r - m) * H[m],
-1LL * H[m],
dp[1][m] + 1LL * m * H[m]
});
}
vector<tuple<int, int, int>> work;
void go(int l, int r) {
if (l >= r) return;
if (l + 1 == r) {
f(t, 2) {
dp[t][l] = H[l];
sp[t].app(0, 0, sp[t].n, l, l + 1, {H[l], 0, (ll)INF});
}
for (int id : qs[l]) {
rez[id] = H[l];
}
return;
}
int m = query(l, r);
// for (int i = l; i < r; i++)
// if (H[i] > H[m])
// m = i;
go(l, m);
go(m + 1, r);
work.emplace_back(l, r, m);
// for (int i = m - 1; i >= l; i--) {
// dp[1][i] = min(
// dp[1][i] + 1LL * (r - m) * H[m],
// dp[1][m] + 1LL * (m - i) * H[m]
// );
// }
}
vector<ll> minimum_costs(vector<int> _H, vector<int> _L,
vector<int> _R) {
L = _L;
R = _R;
H = _H;H = vector<int>(750'000, 3);
init();
dp[0].resize(le(H));
dp[1].resize(le(H));
sp[0] = TS(le(H));
sp[1] = TS(le(H));
qs.resize(le(H));
int Q = L.size();
for (int i = 0; i < Q; i++) {
// int pos = max_element(H.begin() + L[i], H.begin() + R[i] + 1) - H.begin();
int pos = query(L[i], R[i] + 1);
qs[pos].pb(i);
}
rez.resize(Q, (ll)1e18);
// return {};
go(0, le(H));
for (auto ttt : work) {
process(get<0>(ttt), get<1>(ttt), get<2>(ttt));
}
return rez;
}