| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1085290 | vladilius | 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 <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = 1e18;
const int N = 7.5e5;
struct DS{
struct line{
int k; ll b;
ll operator ()(int x){
return 1LL * k * x + b;
}
line(int ks, ll bs){
k = ks; b = bs;
}
};
pil t[4 * N];
pil p[4 * N];
int n;
DS(int ns){
n = ns;
for (int i = 0; i < 4 * n; i++){
t[i] = {0, inf};
p[i] = {0, 0};
}
}
void apply(int v, pil x){
t[v].ff += x.ff; t[v].ss += x.ss;
p[v].ff += x.ff; p[v].ss += x.ss;
}
void push1(int& v, int& tl, int& tr){
int vv = 2 * v;
apply(vv, p[v]);
apply(vv + 1, p[v]);
p[v] = {0, 0};
}
void insert(int v, int tl, int tr, pil f){
if (tl == tr){
if ((1LL * t[v].ff * tl + t[v].ss) > (1LL * f.ff * tl + f.ss)) t[v] = f;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
if (t[v].ff > f.ff) swap(t[v], f);
if ((1LL * f.ff * tm + f.ss) <= (1LL * t[v].ff * tm + t[v].ss)){
swap(t[v], f);
insert(vv + 1, tm + 1, tr, f);
}
else {
insert(vv, tl, tm, f);
}
}
void chmin(int v, int tl, int tr, int& l, int& r, pil& f){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
insert(v, tl, tr, f);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
chmin(vv, tl, tm, l, r, f);
chmin(vv + 1, tm + 1, tr, l, r, f);
}
void chmin(int l, int r, int k, ll b){
pil f = {k, b};
chmin(1, 1, n, l, r, f);
}
void add(int v, int tl, int tr, int& l, int& r, line& f){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
apply(v, {f.k, f.b});
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
add(vv, tl, tm, l, r, f);
add(vv + 1, tm + 1, tr, l, r, f);
}
void add(int l, int r, int k, ll b){
line f(k, b);
add(1, 1, n, l, r, f);
}
ll get(int v, int tl, int tr, int& x){
if (tl == tr) return (1LL * t[v].ff * x + t[v].ss);
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
if (x <= tm){
return min((1LL * t[v].ff * x + t[v].ss), get(vv, tl, tm, x));
}
return min((1LL * t[v].ff * x + t[v].ss), get(vv + 1, tm + 1, tr, x));
}
ll get(int x){
return get(1, 1, n, x);
}
};
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
const int A = 1e9;
int n = (int) H.size(), q = (int) L.size();
vector<int> h(n + 1), aa;
for (int i = 1; i <= n; i++){
h[i] = H[i - 1];
aa.pb(h[i]);
}
sort(aa.begin(), aa.end());
vector<int> vv;
int i = 0;
while (i < n){
int j = i;
while (j < n && aa[i] == aa[j]){
j++;
}
vv.pb(aa[i]);
i = j;
}
vector<int> :: iterator it;
auto pos = [&](int x){
it = lower_bound(vv.begin(), vv.end(), x);
int j = (int) (it - vv.begin());
return j;
};
vector<int> d[(int) vv.size()];
for (int i = 1; i <= n; i++){
d[pos(h[i])].pb(i);
}
vector<int> log(n + 1);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
const int lg = log[n];
int pw[n + 1][lg + 1], pw1[n + 1][lg + 1];
for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i];
for (int j = 1; j <= lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]);
pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]);
}
}
auto get = [&](int l, int r){
int k = log[r - l + 1];
return max(pw[l][k], pw[r - (1 << k) + 1][k]);
};
auto getm = [&](int l, int r){
int k = log[r - l + 1];
return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
};
int f[n + 1], fs = 0;
auto pp = [&](int x, int l, int r){
fs = 0;
int X = pos(x);
it = lower_bound(d[X].begin(), d[X].end(), l);
while (it != d[X].end() && (*it) <= r){
f[fs++] = (*it);
it++;
}
};
pii all1[n + 1]; int s1 = 0;
auto gp = [&](int x, int l, int r){
pp(x, l, r);
s1 = 0;
int pre = l;
for (int j = 0; j < fs; j++){
int i = f[j];
if (pre < i){
all1[s1++] = {pre, i - 1};
}
pre = i + 1;
}
if (pre <= r) all1[s1++] = {pre, r};
};
vector<pii> mp[(int) vv.size()];
function<void(int, int)> build1 = [&](int l, int r){
int m = get(l, r);
mp[pos(m)].pb({l, r});
gp(m, l, r);
vector<pii> all(s1);
for (int i = 0; i < s1; i++) all[i] = all1[i];
for (auto [l1, r1]: all){
build1(l1, r1);
}
};
build1(1, n);
vector<ll> out(q + 1);
vector<vector<arr3>> qs[(int) vv.size()];
for (int i = 0; i < vv.size(); i++){
qs[i].resize(mp[i].size());
}
for (int i = 1; i <= q; i++){
int l, r;
l = L[i - 1]; r = R[i - 1];
l++; r++;
if (get(l, r) == getm(l, r)){
out[i] = 1LL * h[l] * (r - l + 1);
continue;
}
int k = pos(get(l, r)), l1 = 0, r1 = (int) mp[k].size() - 1;
while (l1 + 1 < r1){
int m = (l1 + r1) / 2;
if (mp[k][m].ff <= l){
l1 = m;
}
else {
r1 = m - 1;
}
}
if (mp[k][r1].ff <= l) l1 = r1;
qs[k][l1].pb({l, r, i});
}
DS T1(n), T2(n);
for (int i = 1; i <= n; i++){
T1.add(i, i, 0, -inf);
T2.add(i, i, 0, -inf);
}
vector<int> :: iterator it1, it2;
ll sp[n + 1][lg + 1];
function<void(int, int)> build = [&](int l, int r){
int m = get(l, r);
gp(m, l, r);
vector<pii> all(s1);
for (int i = 0; i < s1; i++) all[i] = all1[i];
for (auto [l1, r1]: all) build(l1, r1);
if (all.empty()){
T1.add(l, r, m, -1LL * m * (l - 1));
T2.add(l, r, -m, 1LL * m * (r + 1));
}
for (auto [l1, r1]: all){
int m1 = get(l1, r1);
gp(m1, l1, r1);
ll mn = inf;
for (int i = 0; i < s1; i++){
// f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1));
auto [l2, r2] = all1[i];
ll F = T1.get(r2);
T1.add(l2, r2, 0, 1LL * m1 * (l2 - l1));
if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1);
mn = min(mn, F - 1LL * m1 * (r2 - l2));
}
mn = inf;
for (int i = s1 - 1; i >= 0; i--){
// f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2));
auto [l2, r2] = all1[i];
ll F = T2.get(l2);
T2.add(l2, r2, 0, 1LL * m1 * (r1 - r2));
if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1);
mn = min(mn, F - 1LL * m1 * (r2 - l2));
}
for (int j = 0; j < fs; j++){
int i = f[j];
ll mn = 1LL * m1 * (i - l1 + 1);
if (i > l1) mn = min(mn, T1.get(i - 1) + m1);
T1.add(i, i, 0, mn - T1.get(i));
}
for (int j = fs - 1; j >= 0; j--){
int i = f[j];
ll mn = 1LL * m1 * (r1 - i + 1);
if (i < r1) mn = min(mn, T2.get(i + 1) + m1);
T2.add(i, i, 0, mn - T2.get(i));
}
}
if (all.empty()) return;
vector<int> x1, y1;
for (auto [l1, r1]: all){
x1.pb(l1); y1.pb(r1);
}
int N = (int) all.size(), LG = log2(N);
for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff));
for (int j = 1; j <= LG; j++){
for (int i = 1; i + (1 << j) <= N + 1; i++){
sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
auto gets = [&](int l, int r){
if (l > r) return inf;
int k = log[r - l + 1];
return min(sp[l][k], sp[r - (1 << k) + 1][k]);
};
int M = pos(m);
int l1 = 0, r1 = (int) mp[M].size() - 1;
while (l1 + 1 < r1){
int m1 = (l1 + r1) / 2;
if (mp[M][m1].ff < l){
l1 = m1 + 1;
}
else {
r1 = m1;
}
}
if (mp[M][r1].ff == l) l1 = r1;
for (auto [ql, qr, i]: qs[M][l1]){
it1 = lower_bound(x1.begin(), x1.end(), ql);
it2 = upper_bound(y1.begin(), y1.end(), qr); it2--;
int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin());
out[i] = gets(i1 + 1, i2 + 1);
if (out[i] != inf) out[i] += 1LL * m * (qr - ql);
if (i1 > 0){
i1--;
if (all[i1].ss >= ql){
out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss));
}
}
if (i2 + 1 < all.size()){
i2++;
if (all[i2].ff <= qr){
out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql));
}
}
}
};
build(1, n);
vector<ll> ret;
for (int i = 1; i <= q; i++) ret.pb(out[i]);
return ret;
}