| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 592943 | Bobaa | 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 <bits/stdc++.h>
using namespace std;
pair<long long, long long> sc[1 << 20];
vector<int> ls, le, nxt, cnt;
vector<int> H, L, R;
vector<long long> ans, pl;
vector<vector<int>> qu;
vector<array<int, 2>> ct;
set<int> sv;
pair<int, int> st[1 << 21];
int vis[1 << 20];
long long getv(int i, int x) {
return sc[i].first * x + sc[i].second;
}
void cal(int u, int l) {
for (int i : qu[u]) {
auto it = --sv.upper_bound(R[i]);
ans[i] = min(ans[i], getv(max(ls[u], min(le[u], *it)), R[i]) + pl[u] - 1ll * H[u] * (L[i] - l));
}
}
void dfs(int u) {
if (u == -1) return;
vis[u] = 1;
auto [l, r] = ct[u];
dfs(l);
dfs(r);
if (l != -1) {
ls[u] = ls[l];
pl[u] = pl[l];
cnt[u] += cnt[l];
}
sc[u] = {H[u], (l != -1 ? getv(le[l], u - 1) + pl[u] : 0) + H[u] - 1ll * u * H[u] - pl[u]};
if (r == -1) {
for (int i : qu[u]) ans[i] = min(ans[i], 1ll * (R[i] - L[i] + 1) * H[u]);
return;
}
pl[r] += 1ll * (u - ls[u] + 1) * H[u];
swap(ls[r], ls[u]);
swap(le[r], le[u]);
swap(pl[r], pl[r]);
cal(u, ls[r]);
swap(ls[r], ls[u]);
swap(le[r], le[u]);
swap(pl[r], pl[u]);
while (nxt[u] <= le[r]) {
if (getv(nxt[u], nxt[nxt[u]] - 1) + pl[r] >= getv(u, nxt[nxt[u]] - 1) + pl[u]) {
sv.erase(nxt[u]);
nxt[u] = nxt[nxt[u]]
cnt[r]--;
}
else if (getv(nxt[u], nxt[u]) + pl[r] < getv(u, nxt[u]) + pl[u]) break;
else {
sv.erase(nxt[u]);
int s = nxt[u], e = nxt[nxt[u]] - 1;
while (s < e) {
int m = (s + e + 1) / 2;
if (getv(nxt[u], m) + pl[r] >= getv(u, m) + pl[u]) s = m;
else e = m - 1;
}
sc[s + 1] = sc[nxt[u]];
nxt[s + 1] = nxt[nxt[u]];
if (nxt[u] == le[r]) le[r] = s + 1;
sv.emplace(s + 1);
nxt[u] = s + 1;
break;
}
}
if (cnt[u] < cnt[r]) {
for (int i = ls[u]; i <= u; i = nxt[i]) sc[i].second += pl[u] - pl[r];
pl[u] = pl[r];
}
else for (int i = nxt[u]; i <= le[r]; i = nxt[i]) sc[i].second += pl[r] - pl[u];
if (nxt[u] <= le[r]) le[u] = le[r];
cnt[u] += cnt[r];
}
vector<long long> minimum_costs(vector<int> hh, vector<int> ll, vector<int> rr) {
int n = hh.size();
H = hh;
L = ll;
R = rr;
ans.resize(L.size(), 1e18);
ct.resize(n, {-1, 1});
qu.resize(n);
pl.resize(n);
ls.resize(n);
le = nxt = cnt = ls;
for (int &i : nxt) i++;
vector<int> pr(n), lc(n, -1), rc(n, -1);
int rt = 0;
for (int i = 1, lst; i < n; i++) {
lst = i - 1;
while (H[lst] < H[i] && lst != rt) lst = pr[lst];
if (H[lst] < H[i]) {
pr[rt] = i;
lc[i] = rt;
rt = i;
}
else if (rc[lst] == -1) {
rc[lst] = i;
pr[i] = lst;
}
else {
pr[rc[lst]] = i;
ic[i] = rc[lst];
rc[lst] = i;
pr[i] = lst;
}
}
for (int i = 0; i < n; i++) ct[i] = {lc[i], rc[i]};
for (int tr = 0; tr < 2; tr++) {
sv.clear();
for (int i = 0; i < n; i++) {
sv.emplace(i);
qu[i].clear();
pl[i] = 0;
ls[i] = i;
cnt[i] = 1;
}
le = nxt = ls;
for (int &i : nxt) i++;
memset(st, 0, sizeof(st));
for (int i = 0; i < n; i++) st[i + (1 << 20)] = {H[i], i * (tr ? 1 : -1)};
for (int i = (1 << 20) - 1; i; i--) st[i] = max(st[i * 2], st[i * 2 + 1]);
auto getmx = [&](int l, int r) {
l += (1 << 20);
r += (1 << 20);
pair<int, int> rt(0, 0);
while (l <= r) {
if (l % 2) {
rt = max(rt, st[l]);
l++;
}
if (r % 2 == 0) {
rt = max(rt, st[r]);
r--;
}
l /= 2;
r /= 2;
}
return rt.second * (tr ? 1 : -1);
};
for (int i = 1; i < L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
dfs(rt);
reverse(H.begin(), H.end());
for (int i = 0; i < L.size(); i++) tie(L[i], R[i]) = make_pair(n - 1 - R[i], n - 1 - L[i]);
rt = n - 1 - rt;
for (auto &[l, r] : ct) tie(l, r) = make_pair(r == -1 ? -1 : n - 1 - r, l == -1 ? -1 : n - 1 - l);
reverse(ct.begin(), ct.end());
}
return ans;
}