Submission #1291911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291911		Icelast	Shopping Plans (CCO20_day2problem3)	C++20	25 / 25	257 ms	63944 KiB

Main

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

const int64_t INF = 1E18;

struct sorted_subsets {
    vector<int64_t> a, ans;
    int l, r;

    using node = tuple<int64_t, int, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;

    sorted_subsets(vector<int64_t> a_, int l_, int r_) : l(l_), r(r_) {
        a = a_;
        sort(a.begin(), a.end());
        if (l == 0) {
            pq.push({0, -1, -1, -1});
        }
        int64_t val = 0;
        for (int i = 0; i < a.size(); i++) {
            val += a[i];
            if (i + 1 >= l && i + 1 <= r) {
                pq.push({val, i, i, a.size()});
            }
        }
    }

    int64_t operator[](int i) {
        while (i >= ans.size()) {
            if (pq.empty()) {
                break;
            }
            auto [v, c, i, h] = pq.top(); pq.pop();
            ans.push_back(v);
            if (c == -1) {
                continue;
            }
            if (i + 1 < h) {
                pq.push({v - a[i] + a[i + 1], c, i + 1, h});
            }
            if (c > 0 && c < i) {
                pq.push({v - a[c - 1] + a[c], c - 1, c, i});
            }
        }
        return i < ans.size() ? ans[i] : INF;
    }
};

void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int64_t>> a(m);
    for (int i = 0; i < n; i++) {
        int u, t; cin >> t >> u; t--;
        a[t].push_back(u);
    }
    vector<sorted_subsets> all;
    for (int i = 0; i < m; i++) {
        int l, r; cin >> l >> r;
        all.push_back(sorted_subsets(a[i], l, r));
    }
    sort(all.begin(), all.end(), [&](auto& u, auto& v) {
        return u[1] - u[0] < v[1] - v[0];
    });

    // value, current index, current pos
    using node = tuple<int64_t, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;
    {
        // make init node
        int64_t val = 0;
        for (int i = 0; i < m; i++) {
            val += all[i][0];
            if (all[i][0] == INF) {
                val = INF;
            }
        }
        pq.push({val, -1, 0});
    }
    for (int it = 0; it < k; it++) {
        if (pq.empty()) {
            cout << "-1\n"; continue;
        }
        auto [v, i, p] = pq.top(); pq.pop();
        if (v >= INF) {
            cout << "-1\n"; continue;
        }
        cout << v << '\n';
        // add 1 to current index
        if (i != -1) {
            pq.push({v + all[i][p + 1] - all[i][p], i, p + 1});
        }
        // push 1 to next index
        if (i + 1 < m) {
            pq.push({v + all[i + 1][1] - all[i + 1][0], i + 1, 1});
        }
        // remove 1 from current and push 1 to next index (only applicable when p = 1)
        if (p == 1 && i + 1 < m) {
            pq.push({v + all[i + 1][1] - all[i + 1][0] + all[i][0] - all[i][1], i + 1, 1});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5