Submission #221520

#	Time	Username	Problem	Language	Result	Execution time	Memory
221520		IgorI	Meetings (IOI18_meetings)	C++17	0 / 100	5556 ms	28164 KiB

meetings

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

const int N = 800000;

int n, q;

int H[N];
pair<int, int> sp[20][N];

pair<int, int> spmax(int l, int r, int id)
{
    int len = r - l + 1;
    int jj = H[len];
    if (id == 0)
    {
        return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
    }
    else
    {
        if (sp[jj][l].first != sp[jj][r - (1 << jj) + 1].first)
            return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
        else
            return min(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
    }
}

bool comp1(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first)
        return a < b;
    else
        return a > b;
}

vector<long long> solve(vector<int> h, vector<int> l, vector<int> r, int id)
{
    vector<long long> cur_values(n, -1);
    vector<long long> re_ans(q);
    vector<pair<int, int> > order;
    for (int i = 0; i < n; i++)
    {
        order.push_back({h[i], i});
    }
    if (id == 0) sort(order.begin(), order.end());
    else sort(order.begin(), order.end(), comp1);

    for (int i = 0; i < n; i++)
    {
        sp[0][i] = {h[i], i};
    }
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)
        {
            sp[j][i] = spmax(i, i + (1 << j) - 1, id);
        }
    }

    vector<vector<int> > queries_here(n);
    for (int j = 0; j < q; j++)
    {
        queries_here[spmax(l[j], r[j], id).second].push_back(j);
    }

    #ifdef LOCAL
        cout << "Solution\n";
    #endif // LOCAL
    for (auto it : order)
    {
        int cnt = 0;
        cur_values[it.second] = 0;
        #ifdef LOCAL
            for (int i = 0; i < n; i++) cout << cur_values[i] << " ";
            cout << endl;
        #endif // LOCAL
        for (int i = 0; i < queries_here[it.second].size(); i++)
        {
            int j = queries_here[it.second][i];
            re_ans[j] = cur_values[r[j]] + (it.second - l[j] + 1) * it.first;
        }
        for (int i = it.second; i >= 0; i--)
        {
            if (cur_values[i] == -1) break;
            cnt++;
        }
        for (int i = it.second; i < n; i++)
        {
            if (cur_values[i] == -1) break;
            cur_values[i] = cur_values[i] + cnt * it.first;
        }
        for (int i = it.second; i < n; i++)
        {
            if (cur_values[i] == -1) break;
            if (i > 0 && cur_values[i - 1] != -1) cur_values[i] = min(cur_values[i], cur_values[i - 1] + it.first);
        }
    }
    return re_ans;
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r)
{
    H[1] = 0, H[2] = 0, H[3] = 1;
    for (int i = 4; i < N; i++)
    {
        H[i] = H[i - 1];
        if (((i - 1) & (i - 2)) == 0)
        {
            H[i]++;
        }
    }
    n = h.size(), q = l.size();
    vector<long long> res1 = solve(h, l, r, 0);
    reverse(h.begin(), h.end());
    for (int i = 0; i < q; i++)
    {
        l[i] = n - l[i] - 1;
        r[i] = n - r[i] - 1;
        swap(l[i], r[i]);
    }
    vector<long long> res2 = solve(h, l, r, 1);
    vector<long long> ans(q);
    for (int i = 0; i < q; i++)
    {
        ans[i] = min(res1[i], res2[i]);
    }
    #ifdef LOCAL
        for (int i = 0; i < q; i++) cout << res1[i] << " "; cout << "\n";
        for (int i = 0; i < q; i++) cout << res2[i] << " "; cout << "\n";
    #endif // LOCAL
    return ans;
}

#ifdef LOCAL
int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> h(n);
    vector<int> l(q), r(q);
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < q; i++) cin >> l[i] >> r[i];
    vector<long long> ans = minimum_costs(h, l, r);
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
#endif // LOCAL

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> solve(std::vector<int>, std::vector<int>, std::vector<int>, int)':
meetings.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < queries_here[it.second].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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