| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 797832 | resting | 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;
#define ll long long
int n, q;
vector<ll> helper(vector<int> h, vector<int> l, vector<int> r) {
vector<vector<pair<int, int>>> qq(n);
for (int i = 0; i < q; i++) qq[r[i]].push_back({ l[i], i });
vector<ll> c(q);
ll curad = 0;
set <pair<int, pair<ll, ll>>> s; //position, {const, slope}
vector<pair<int, pair<ll, int>>> st; // index, {value, height}
vector<vector<int>> overtake(n + 1);
auto find_overtake = [&](pair<ll, ll> a, pair<ll, ll>b) -> int { // when a overtakes b as smallest iykyk
assert(b.second >= a.second); // or its the other way around
if (a.first <= b.first && a.second <= b.second) return 0;
if (b.first >= a.first && b.second >= a.second) return n;
//first i when b.first + b.second * i > a.first + a.second * i
// (b.second - a.second) * i > a.first - b.first
// i > (a.first - b.first) / a.second - b.second
int div = b.second - a.second;
return (int)min((ll)n, (a.first - b.first + (div - 1)) / div);
};
for (int i = 0; i < n; i++) {
//cout << h[i] << endl;
while (st.size() && st.back().second.second < h[i]) st.pop_back();
if (st.size())curad = st.back().second.first + (i - st.back().first) * h[i];
else curad = (i + 1) * h[i];
st.push_back({ i, {curad, h[i]} });
//merge set
ll mn = curad - h[i] * i;int mni = i;
while (s.size() && prev(s.end())->second.second <= h[i]) {
ll t = prev(s.end())->second.first + prev(s.end())->second.second * (i - 1) - h[i] * (i - 1);
if (t < mn) {
mn = t; mni = prev(s.end())->first;
}
//cout << "erased: " << prev(s.end())->first << endl;
s.erase(prev(s.end()));
}
s.insert({ mni, {mn, h[i]} });
//cout << "insert: " << mni << "," << mn << "," << h[i] << endl;
if (s.size() > 1) {
overtake[max(i, min(n, find_overtake(prev(s.end())->second, prev(prev(s.end()))->second)))].push_back(prev(s.end())->first);
}
for (int k = 0; k < overtake[i].size(); k++) {
auto& x = overtake[i][k];
auto t = s.lower_bound({ x, {0LL, 0LL} });
if (t == s.begin() || t == s.end() || t->first != x) continue;
auto p = prev(t);
if (p->second.first + p->second.second * i < t->second.first + t->second.second * i) continue;
//cout << "erased: " << p->first << endl;
s.erase(p);
if (t == s.begin()) continue;
auto pp = prev(t);
overtake[max(i, min(n, find_overtake(t->second, pp->second)))].push_back(t->first);
}
for (auto& x : qq[i]) {
c[x.second] = 1e18;
int l = x.first;
auto owo = lower_bound(st.begin(), st.end(), pair<int, pair<ll, int>>({ l, {(ll)-1e18, (int)-1e9 }));
auto lll = s.lower_bound({ owo->first, {(ll)-1e18, (ll)-1e18} });
if (lll == s.end()) continue;
//cout << x.second << " ans " << lll->second.first << " " << lll->second.second << " " << i << " " << owo->second.first << " " << owo->first << " " << owo->second.second << endl;
c[x.second] = lll->second.first + lll->second.second * i - owo->second.first + (owo->first - l + 1) * owo->second.second;
}
}
//cout << endl;
return c;
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n = h.size(); q = l.size();
vector<ll> a = helper(h, l, r);
reverse(h.begin(), h.end());
for (int i = 0; i < q; i++) { swap(l[i], r[i]); l[i] = n - 1 - l[i]; r[i] = n - 1 - r[i]; }
vector<ll> b = helper(h, l, r);
vector<ll> c(q); for (int i = 0; i < q;i++) c[i] = min(a[i], b[i]);
return c;
}
int32_t main() {
vector<ll> c = minimum_costs({ 5 , 5 }, { 0 }, { 1 });
for (auto& x : c) cout << x << " ";
cout << endl;
}