Submission #797894

#	Time	Username	Problem	Language	Result	Execution time	Memory
797894		resting	Meetings (IOI18_meetings)	C++17	100 / 100	1785 ms	154552 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n, q;

vector<ll> helper(vector<int32_t> h, vector<int32_t> l, vector<int32_t> 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 + (ll)(i - st.back().first) * h[i];
        else curad = (ll)(i + 1) * h[i];
        st.push_back({ i, {curad, h[i]} });

        //merge set
        ll mn = curad - (ll)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) - (ll)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]} });
        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, {(ll)-1e18, (ll)-1e18} });
            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 } }));
            assert(owo != st.end());
            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 + (ll)(owo->first - l + 1) * owo->second.second;
        }
    }

    //cout << endl;
    return c;
}

vector<ll> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> 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]);
    for (int i = 0; i < q; i++) {
        if (c[i] == 1e18)
            c[i] = (ll)(r[i] - l[i] + 1) * h[l[i]];
    }
    return c;
}

// vector<ll> minimum_costs_correct(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r) {
//     n = h.size(); q = l.size();
//     vector<ll> c(q);
//     for (int i = 0; i < q; i++) {
//         c[i] = 1e18;
//         for (int j = l[i]; j <= r[i]; j++) {
//             ll res = 0;
//             ll mx = h[j];
//             for (int k = j; k <= r[i]; k++) {
//                 mx = max(mx, (ll)h[k]); res += mx;
//             }
//             mx = h[j];
//             for (int k = j - 1; k >= l[i]; k--) {
//                 mx = max(mx, (ll)h[k]); res += mx;
//             }
//             c[i] = min(c[i], res);
//         }
//     }
//     return c;
// }

// int32_t main() {
//     for (int i = 0; i < 1000; i++) {
//         vector<int> h(10), l(1), r(1);
//         for (int z = 0; z < 10; z++) h[z] = rand() % 7;
//         l[0] = rand() % 4; r[0] = rand() % 6 + l[0];
//         vector<ll> c1 = minimum_costs(h, l, r);
//         vector<ll> c2 = minimum_costs_correct(h, l, r);
//         if (c1 != c2) {
//             cout << "test # " << i << endl;
//             for (auto& x : h) cout << x << " "; cout << endl;
//             for (auto& x : l) cout << x << " "; cout << endl;
//             for (auto& x : r) cout << x << " "; cout << endl;
//             for (auto& x : c1) cout << x << " "; cout << endl;
//             for (auto& x : c2) cout << x << " "; cout << endl;
//             cout << endl;
//         }
//     }
// }

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> helper(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int k = 0; k < overtake[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40