Zadanie meteory finał XVIII OI, równoległe wyszukiwanie binarne

Question

Mam problem z zadaniem meteory z finału XVIII OI: https://szkopul.edu.pl/problemset/problem/czzVm7v3I58TnPHzBgWiyELT/site/?key=statement

Zobaczyłem je w przygodach, trochę nad nim pomyślałem, przeczytałem rozwiązanie i wydawało mi się, że je rozumiem, robimy zwykłe wyszukiwanie binarne, ale żeby nie robić dła każdego oddzielnie, to robimy je równolegle, czyli trzymamy rekurencyjnie i dzielimy je na części. Wszystko było fajnie, nawet się ucieszyłem, że poznałem nowy algorytm, napisałem go, uśmiechnięty, że będzie setka, a tu się okazało, że jest zero i w wszystkich testach oprócz 3 przykładowych przekroczono limit czasu. Kompletnie nie wiem o co chodzi. Kod wydaje się być prosty. Czyli najprawdopodobniej nie rozumiem tej idei...

Strona 184 w książeczce OI, to rozwiązanie, co wydaje mi się, że je rozumiem. Znaczy wydawało mi się, bo teraz to wiem, że czegoś nie rozumiem, tylko jeszcze nie wiem czego.

Mój kod:

#include <iostream>
#include <vector>

using namespace std;

struct Opad
{
    int l;
    int r;
    int ile_dod;
};

int n = 0, m = 0, k = 0, base = (1 << 19), rozmiar_drzewa = base * 2;
vector<int> drzewo_przedzialowe;
vector<int> idxy_poczatkowe;
vector<int> zapotrzebowanie;
vector<int> stacje;
vector<int> wyn;
vector<Opad> opady;

inline void update (int l, int p, int val)
{
    l = l + base - 1, p = p + base + 1;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            drzewo_przedzialowe[l+1] += val;
        if (p % 2 == 1)
            drzewo_przedzialowe[p-1] += val;
        l /= 2;
        p /= 2;
    }
}

inline void dodaj (int l, int p, int val)
{
    if (l <= p)
        update(l,p,val);
    else
    {
        update(l,m-1,val);
        update(0,p,val);
    }
}

inline int query(int v)
{
    v += base;
    int res = 0;
    while (v > 0)
    {
        res += drzewo_przedzialowe[v];
        v /= 2;
    }
    return res;
}

inline void clearuj_drzewo_przedzialowe()
{
    drzewo_przedzialowe.assign(rozmiar_drzewa,0);
}

inline void binary_searchh(int l, int p, vector<int> idxy)
{
    if (p - l == 1)
    {
        for (int i = 0; i < idxy.size(); ++i)
            wyn[idxy[i]] = p;
    }
    else
    {
        int srodek = (l + p) / 2;
        clearuj_drzewo_przedzialowe();
        for (int i = 0; i < srodek; ++i)
            dodaj(opady[i].l-1, opady[i].r-1, opady[i].ile_dod);
        vector<int> ile;
        ile.assign(n+1,0);
        for (int i = 0; i < m; ++i)
            ile[stacje[i]] += query(i);
        vector<int> vect_lewych, vect_prawych;
        for (int i = 0; i < idxy.size(); ++i)
        {
            if (ile[idxy[i]] >= zapotrzebowanie[idxy[i]])
                vect_prawych.push_back(idxy[i]);
            else
                vect_lewych.push_back(idxy[i]);
        }
        binary_searchh(l,srodek,vect_prawych);
        binary_searchh(srodek,p,vect_lewych);
    }
}

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

    cin >> n >> m;

    zapotrzebowanie.assign(n+1,-1);
    wyn.assign(n+1,-1);
    stacje.assign(m,-1);

    for (int i = 0; i < m; ++i)
        cin >> stacje[i];

    for (int i = 1; i <= n; ++i)
        cin >> zapotrzebowanie[i];

    cin >> k;
    opady.assign(k,{});
    for (int i = 0; i < k; ++i)
        cin >> opady[i].l >> opady[i].r >> opady[i].ile_dod;

    clearuj_drzewo_przedzialowe();
    idxy_poczatkowe.assign(n,0);
    for (int i = 0; i < n; ++i)
        idxy_poczatkowe[i] = i+1;
    binary_searchh(-1,k+1,idxy_poczatkowe);

    for (int i = 1; i <= n; ++i)
    {
        if (wyn[i] == k+1)
            cout << "NIE" << '\n';
        else
            cout << wyn[i] << '\n';
    }

    return 0;
}

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

Comments

Już chyba rozumiem, że to jest za wolne, i trzeba to normalnie iterscyjnie trzymać, chyba wiem jak to zrobić.

Answer 1

Przeszło na 100pkt. Mój problem był taki, że nie rozumiałem idei równoległego wyszukiwania binarnego. To co tam naklepałem ma TLE, bo jest conajmiej O(N^2 * lg N), jak nie więcej. Ono jest trikiem jak mając dane N zdarzeń i dla każdego puścić wyszukiwanie binarne, przyśpieszyć to pusczając to raz. Cała idea jest taka, że jak dla kolejnych zdarzeń trzeba sprawdzić stan po np. 5, 3, 10 deszczach, to zamiast symulować z drzewem przedziałowym dla każdego z N miast kolejne deszcze, to robimy to tak jakby gąsienicą. Naliczamy stan po 3 deszczach, sprawdzamy dla tego, co interesuje nas po 3 deszczach i potem jak mamy po 5 deszczach, to nie naliczamy od nowa, tylko do tego stanu po 3 deszczach dokładamy po 4,5, sprawdzamy dla tego po 5, potem dla tego po dziesięciu nie liczymy od nowa, tylko do tego co mamy(po pięciu) dokładamy po 6,7,8,9,10. I tak dla wszystkich elementów. Dlatego to jest szybkie, bo nie naliczamy dla każdego od nowa. Chyba najłatwiej te zdarzenia posortować od najmiejszych(ja tak zrobiłem) Świetna technika! Bardzo mi się podoba.

Kod:

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

using namespace std;
typedef long long ll;

struct Opad
{
    int l;
    int r;
    int ile_dod;
};

struct Element
{
    int l;
    int p;
    int srodek;
    int idx_miasta;
    bool operator < (const Element &element) const
    {
        return srodek < element.srodek;
    }
};

int n = 0, m = 0, k = 0, base = (1 << 19), rozmiar_drzewa = base * 2;
vector<ll> drzewo_przedzialowe;
vector<int> zapotrzebowanie;
vector<int> stacje;
vector<int> wyn;
vector<Opad> opady;
vector<vector<int>> jakie_idxy_ma_miasto;
vector<Element> elementy;

inline void update (int l, int p, ll val)
{
    l = l + base - 1, p = p + base + 1;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            drzewo_przedzialowe[l+1] += val;
        if (p % 2 == 1)
            drzewo_przedzialowe[p-1] += val;
        l /= 2;
        p /= 2;
    }
}

inline void dodaj (int l, int p, ll val)
{
    if (l <= p)
        update(l,p,val);
    else
    {
        update(l,m-1,val);
        update(0,p,val);
    }
}

inline ll query(int v)
{
    v += base;
    ll res = 0;
    while (v > 0)
    {
        if (drzewo_przedzialowe[v] > 1e9) // Zeby nie przekroczylo sie z long longa.
            return 1e9+5;
        res += drzewo_przedzialowe[v];
        v /= 2;
    }
    return res;
}

inline void clearuj_drzewo_przedzialowe()
{
    drzewo_przedzialowe.assign(rozmiar_drzewa,0);
}

int main()
{
    // Rownolegle wyszukiwanie binarne po wyniku, https://forum.pasja-informatyki.pl/583882/zadanie-meteory-final-xviii-oi-rownolegle-wyszukiwanie-binarne?show=583891#a583891
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    zapotrzebowanie.assign(n+1,-1);
    wyn.assign(n+1,-1);
    stacje.assign(m,-1);
    jakie_idxy_ma_miasto.assign(n+1,{});

    for (int i = 0; i < m; ++i)
        cin >> stacje[i];

    for (int i = 0; i < m; ++i)
        jakie_idxy_ma_miasto[stacje[i]].push_back(i);

    for (int i = 1; i <= n; ++i)
        cin >> zapotrzebowanie[i];

    cin >> k;
    opady.assign(k,{});
    for (int i = 0; i < k; ++i)
        cin >> opady[i].l >> opady[i].r >> opady[i].ile_dod;

    for (int i = 1; i <= n; ++i)
        elementy.push_back({0,k+1,(k+1) / 2, i});
    sort(elementy.begin(), elementy.end());

    while(!elementy.empty())
    {
        int wsk = 0;
        vector<Element> nowy;
        clearuj_drzewo_przedzialowe();
        for (int i = 0; i < k and wsk < elementy.size(); ++i)
        {
            dodaj(opady[i].l-1, opady[i].r-1, opady[i].ile_dod);
            while(true)
            {
                if (elementy[wsk].srodek - 1 == i)
                {
                    ll sum = 0;
                    for (int j = 0; j < jakie_idxy_ma_miasto[elementy[wsk].idx_miasta].size(); ++j)
                        sum += query(jakie_idxy_ma_miasto[elementy[wsk].idx_miasta][j]);
                    int poczatek = 0, koniec = 0;
                    if (sum >= zapotrzebowanie[elementy[wsk].idx_miasta] or sum > 1e9)
                    {
                        poczatek = elementy[wsk].l, koniec = elementy[wsk].srodek;
                    }
                    else
                    {
                        poczatek = elementy[wsk].srodek, koniec = elementy[wsk].p;
                    }
                    if (koniec - poczatek == 1)
                        wyn[elementy[wsk].idx_miasta] = koniec;
                    else
                        nowy.push_back({poczatek, koniec, (poczatek + koniec) / 2, elementy[wsk].idx_miasta});
                    wsk++;
                }
                else
                    break;
            }
        }
        elementy = nowy;
        sort(elementy.begin(), elementy.end());
    }

    for (int i = 1; i <= n; ++i)
    {
        if (wyn[i] == k+1)
            cout << "NIE" << '\n';
        else
            cout << wyn[i] << '\n';
    }

    return 0;
}