Zadanie Wskaźnik Hirscha finał OIG

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/diIixmpgLnmLnihDYGeaDwYQ/site/?key=statement

Samo zadanie wydało mi się łatwe. Sortuje elementy od najmniejszych wymaganych publikacji i idę od góry zachłanem z setem, żeby naliczyć koszt[v] = min koszt biorąc A[v] elementów. I potem dla każdego zapytania się bin searchuję po kosztach. Napisałem kod i dostaję całą masę WA, i nie wiem, gdzie jest błąd:

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

using namespace std;
typedef long long ll;

struct Element
{
    ll ile_cytowan;
    ll cena;
    bool operator < (const Element &element) const
    {
        return ile_cytowan < element.ile_cytowan;
    }
};

ll n = 0, q = 0;
ll suma = 0;
vector<Element> elementy;
vector<ll> koszty;
multiset<ll> S;

inline void napelniaj()
{
    koszty.assign(n,1e18+20);
    for (int i = n-1; i >= 0; --i)
    {
        suma += elementy[i].cena;
        S.insert(elementy[i].cena);
        while(S.size() > elementy[i].ile_cytowan)
        {
            ll val = *S.rbegin();
            suma -= val;
            S.erase(S.lower_bound(val));
        }
        if (S.size() == elementy[i].ile_cytowan)
            koszty[i] = suma;
    }
}

inline ll zapytanie()
{
    ll wartosc;
    cin >> wartosc;

    int poczatek = -1, koniec = n, srodek = 0;
    while(koniec - poczatek > 1)
    {
        srodek = (poczatek + koniec) / 2;
        if (wartosc >= koszty[srodek])
            poczatek = srodek;
        else
            koniec = srodek;
    }

    if (poczatek == -1)
        return 0;
    else
        return elementy[poczatek].ile_cytowan;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    elementy.assign(n,{});
    for (int i = 0; i < n; ++i)
        cin >> elementy[i].ile_cytowan >> elementy[i].cena;
    sort(elementy.begin(), elementy.end());

    napelniaj();

    while(q--)
        cout << zapytanie() << '\n';

    return 0;
}

Program zazwyczaj daje lekko za małe odpowiedzi.

edit: usunąłem jednego if-a w operatorze bo i tak nic nie dawał.

Z góry dziękuję za pomoc i poświęcony czas!

Comments

Chyba znalazłem błąd w pomyśle.

Answer 1

Pomysł był dobry, tylko złe było założenie, ży wynik musi być wsród prac. Ważne spostrzerzenie jest takie, że wynik nie może być > n, ponieważ nie będzie dało się do ułożyć za pomocą n prac. Skoro N <= 2*10^5, to możemy sobie na spokojnie naliczyć koszt[v] dla każdego v >= 0 oraz v <= n. Znając to robimy praktycznie to samo. O(N lg N + Q lg N) - 100pkt:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

struct Element
{
    int ile_cytowan;
    int cena;
    bool operator < (const Element &element) const
    {
        return ile_cytowan < element.ile_cytowan;
    }
};

int n = 0, q = 0, wsk = 0;
ll suma = 0;
vector<Element> elementy;
vector<ll> koszty;
priority_queue<int> Q;

inline void napelniaj()
{
    koszty.assign(n+1,1e18+20);
    wsk = n-1;
    for (int i = n; i >= 0; --i)
    {
        while(wsk >= 0)
        {
            if (elementy[wsk].ile_cytowan >= i)
            {
                suma += elementy[wsk].cena;
                Q.push(elementy[wsk].cena);
                wsk--;
            }
            else
                break;
        }
        while(Q.size() > i)
        {
            ll val = Q.top();
            suma -= val;
            Q.pop();
        }
        if (Q.size() == i)
            koszty[i] = suma;
    }
}

inline ll zapytanie()
{
    ll wartosc;
    cin >> wartosc;

    int poczatek = 0, koniec = n+1, srodek = 0;
    while(koniec - poczatek > 1)
    {
        srodek = (poczatek + koniec) / 2;
        if (wartosc >= koszty[srodek])
            poczatek = srodek;
        else
            koniec = srodek;
    }
    return poczatek;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    elementy.assign(n,{});
    for (int i = 0; i < n; ++i)
        cin >> elementy[i].ile_cytowan >> elementy[i].cena;
    sort(elementy.begin(), elementy.end());

    napelniaj();

    while(q--)
        cout << zapytanie() << '\n';

    return 0;
}