Submission #576727

#	Time	Username	Problem	Language	Result	Execution time	Memory
576727		eecs	Shopping Plans (CCO20_day2problem3)	C++17	25 / 25	375 ms	47920 KiB

Main

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

typedef long long ll;
const int maxn = 200010;
int n, m, K, id[maxn];
ll ans;

struct {
    int l, r;
    vector<int> c;
    vector<ll> w;
    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<>> Q;

    bool init() {
        if (l > c.size()) return 1;
        sort(c.begin(), c.end());
        r = min(r, (int)c.size());
        if (!r) return w = {0}, 0;
        if (!l) w = {0};
        ans += accumulate(c.begin(), c.begin() + l, 0LL);
        ll s = 0;
        for (int i = l; i < r; i++) {
            if (i) Q.emplace(s, i - 1, i, c.size() + 1);
            s += c[i];
        }
        Q.emplace(s, r - 1, r, c.size() + 1);
        return 0;
    }
    void inc() {
        if (Q.empty()) return w.push_back(1e18);
        auto p = Q.top(); Q.pop();
        w.push_back(get<0>(p));
        if (get<2>(p) + 1 < get<3>(p)) {
            Q.emplace(get<0>(p) + c[get<2>(p)] - c[get<2>(p) - 1], get<1>(p), get<2>(p) + 1, get<3>(p));
        }
        if (get<1>(p) && get<1>(p) + 1 < get<2>(p)) {
            Q.emplace(get<0>(p) + c[get<1>(p)] - c[get<1>(p) - 1], get<1>(p) - 1, get<1>(p) + 1, get<2>(p));
        }
    }
    ll operator [] (int k) {
        while (k >= w.size()) inc();
        return w[k];
    }
} V[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> K;
    while (n--) {
        int x, y;
        cin >> x >> y;
        V[x].c.push_back(y);
    }
    for (int i = 1; i <= m; i++) {
        cin >> V[i].l >> V[i].r;
        if (V[i].init()) {
            while (K--) cout << "-1\n";
            exit(0);
        }
    }
    iota(id + 1, id + m + 1, 1);
    sort(id + 1, id + m + 1, [&](int i, int j) -> bool {
        return V[i][1] - V[i][0] < V[j][1] - V[j][0];
    });
    cout << ans << "\n", K--;
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> Q;
    Q.emplace(V[id[1]][1] - V[id[1]][0], 1, 2);
    while (K && !Q.empty()) {
        auto p = Q.top(); Q.pop();
        if (get<0>(p) > 1e17) break;
        cout << ans + get<0>(p) << "\n", K--;
        int x = id[get<1>(p)], y = id[get<1>(p) + 1];
        Q.emplace(get<0>(p) + V[x][get<2>(p)] - V[x][get<2>(p) - 1], get<1>(p), get<2>(p) + 1);
        if (get<1>(p) < m) {
            Q.emplace(get<0>(p) + V[y][1] - V[y][0], get<1>(p) + 1, 2);
            if (get<2>(p) == 2) Q.emplace(get<0>(p) + V[y][1] - V[y][0] - V[x][1] + V[x][0], get<1>(p) + 1, 2);
        }
    }
    while (K--) cout << "-1\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'bool<unnamed struct>::init()':
Main.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if (l > c.size()) return 1;
      |             ~~^~~~~~~~~~
Main.cpp: In member function 'll<unnamed struct>::operator[](int)':
Main.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (k >= w.size()) inc();
      |                ~~^~~~~~~~~~~

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