• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Kinoman 1 etap XXII OI, drzewo przedziałowe przedział - przedział, przekroczono limit czasu

VPS Starter Arubacloud
0 głosów
360 wizyt
pytanie zadane 19 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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

Zrobiłem mniej więcej takim pomysłem, jak jest opisane w książeczce z XXII OI: https://oi.edu.pl/l/22oi_ksiazeczka/

Robie sumy prefiksowe. Pierwsze wystąpienie dodaje do sum prefiksowych wartość koszty[i], drugie odejmuje koszty[j], a późniejsze nic nie robią, chyba że w aktualizacjach one staną się wcześniejsze. W książeczce OI napisali, że można to zrobić drzewem przedziałowym i tyle.

Ja napisałem drzewo przedzial-przedział (dodaj na przedziale, odczytaj maxa na przedziale), ale dostaję tylko 33pkt(przekroczono limit czasu), wydaje mi się, to trochę dziwne, ale nie wiem co zrobić innaczej. Kod:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, m = 0, base = (1 << 20), rozmiar_drzewa = base * 2;
ll suma = 0, wyn = 0;
vector<int> liczby;
vector<vector<int>> wystapienia;
vector<int> koszty;
vector<int> wystapienia_wsk;
vector<ll> tree;
vector<ll> tree2;

inline ll querry_max(int l_kontrolowane, int p_kontrolowane, int l_zap, int p_zap, int v)
{
    if (l_kontrolowane > p_zap or p_kontrolowane < l_zap)
        return 0;
    else if (l_kontrolowane >= l_zap and p_kontrolowane <= p_zap)
        return tree[v];
    else if (l_kontrolowane != p_kontrolowane)
    {
        if (tree2[v] != 0)
        {
            tree2[v*2+1] += tree2[v];
            tree2[v*2] += tree2[v];
            tree[v*2+1] += tree2[v];
            tree[v*2] += tree2[v];
            tree2[v] = 0;
        }
        return max(querry_max(l_kontrolowane,l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1 - 2) / 2,l_zap,p_zap,v*2), querry_max(l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1) / 2,p_kontrolowane,l_zap,p_zap,v*2+1));
    }
}

inline void update (int l_kontrolowane, int p_kontrolowane, int l_zap, int p_zap, int v, int val)
{
    //cout << "V: " << v << endl;
    if (l_kontrolowane > p_zap or p_kontrolowane < l_zap)
        return;
    else if (l_kontrolowane >= l_zap and p_kontrolowane <= p_zap)
    {
        tree[v] += val;
        tree2[v] += val;
    }
    else if (l_kontrolowane != p_kontrolowane)
    {
        if (tree2[v] != 0)
        {
            tree2[v*2+1] += tree2[v];
            tree2[v*2] += tree2[v];
            tree[v*2+1] += tree2[v];
            tree[v*2] += tree2[v];
            tree2[v] = 0;
        }
        update(l_kontrolowane,l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1 - 2) / 2,l_zap,p_zap,v*2,val);
        update(l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1) / 2,p_kontrolowane,l_zap,p_zap,v*2+1,val);
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
}

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

    cin >> n >> m;

    tree.assign(rozmiar_drzewa,0);
    tree2.assign(rozmiar_drzewa,0);

    liczby.assign(n,-1);
    for (int i = 0; i < n; ++i)
        cin >> liczby[i];

    wystapienia.assign(1e6+1,{});
    wystapienia_wsk.assign(1e6+1,0);
    for (int i = 0; i < n; ++i)
        wystapienia[liczby[i]].push_back(i);

    koszty.assign(m+1,-1);
    for (int i = 1; i <= m; ++i)
        cin >> koszty[i];

    for (int i = 0; i < n; ++i)
    {
        if (wystapienia_wsk[liczby[i]] == 0)
            suma += koszty[liczby[i]];
        else if (wystapienia_wsk[liczby[i]] == 1)
            suma -= koszty[liczby[i]];
        wystapienia_wsk[liczby[i]]++;
        update(1,base,i+1,i+1,1,suma);
    }

    fill(wystapienia_wsk.begin(), wystapienia_wsk.end(), 0);


    ll ile_dod = 0;
    for (int i = 0; i < n; ++i)
    {
        wyn = max(wyn, querry_max(1,base,i+1,n,1) + ile_dod);
        int val = liczby[i];
        if (wystapienia_wsk[val] + 1 == wystapienia[val].size())
            ile_dod += -koszty[val];
        else if (wystapienia_wsk[val] + 2 == wystapienia[val].size())
        {
            ile_dod += -koszty[val];
            update(1,base, wystapienia[val][wystapienia_wsk[val]+1]+1,n,1,2 * koszty[val]);
        }
        else
        {
            ile_dod += -koszty[val];
            update(1,base,wystapienia[val][wystapienia_wsk[val]+1]+1,n,1,2 * koszty[val]);
            update(1,base,wystapienia[val][wystapienia_wsk[val]+2]+1,n,1,-koszty[val]);
        }
        wystapienia_wsk[val]++;
    }

    cout << wyn << '\n';

    return 0;
}

Co ciekawe samo napełnienie drzewa początkowe zajmuje mniej więcej połowę czasu.

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

komentarz 19 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Nie rozumiem dokładnie jak akutalizujesz te przedziały, ale jeśli odpowiednio to zrobisz to potem powinno wystarczyć zrobić maksa na całym przedziale, co będzie działało w czasie stałym
komentarz 19 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Zmieniłem to i jeszcze, że początkowo napełnia liniowo, ale przchodzi niestesty tylko na 89pkt. Chyba poprostu nie dobiję tego do 100pkt. 2 testy nie przechodzą czasowo
1
komentarz 19 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

ooo przeszło na 100pkt. Dużo czasu w updatach zabierało to, że robiłem updata na przedziale [x,n], a mogłem na przedziale [x,base] i wtedy szybciej by się skończył. Kod dający 100pkt:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, m = 0, base = 0, rozmiar_drzewa = 0, dod_update = 0, l_zap = 0;
ll suma = 0, wyn = 0, ile_dod = 0;
vector<int> liczby;
vector<vector<int>> wystapienia;
vector<int> koszty;
vector<int> wystapienia_wsk;
vector<ll> tree;
vector<ll> tree2;

inline void update (int l_kontrolowane, int p_kontrolowane, int v)
{
    if (l_kontrolowane > base or p_kontrolowane < l_zap)
        return;
    else if (l_kontrolowane >= l_zap and p_kontrolowane <= base)
    {
        tree[v] += dod_update;
        tree2[v] += dod_update;
    }
    else if (l_kontrolowane != p_kontrolowane)
    {
        if (tree2[v] != 0)
        {
            tree2[v*2+1] += tree2[v];
            tree2[v*2] += tree2[v];
            tree[v*2+1] += tree2[v];
            tree[v*2] += tree2[v];
            tree2[v] = 0;
        }
        update(l_kontrolowane,l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1 - 2) / 2,v*2);
        update(l_kontrolowane + (p_kontrolowane - l_kontrolowane + 1) / 2,p_kontrolowane,v*2+1);
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
}

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

    cin >> n >> m;

    base = (1 << int(ceil(log2(n+1))));
    rozmiar_drzewa = base * 2;

    tree.assign(rozmiar_drzewa,0);
    tree2.assign(rozmiar_drzewa,0);

    liczby.assign(n,-1);
    for (int i = 0; i < n; ++i)
        cin >> liczby[i];

    wystapienia.assign(1e6+1,{});
    wystapienia_wsk.assign(1e6+1,0);
    for (int i = 0; i < n; ++i)
        wystapienia[liczby[i]].push_back(i);

    koszty.assign(m+1,-1);
    for (int i = 1; i <= m; ++i)
        cin >> koszty[i];

    for (int i = 0; i < n; ++i)
    {
        if (wystapienia_wsk[liczby[i]] == 0)
            suma += koszty[liczby[i]];
        else if (wystapienia_wsk[liczby[i]] == 1)
            suma -= koszty[liczby[i]];
        wystapienia_wsk[liczby[i]]++;
        tree[base+i] = suma;
    }

    for (int i = base-1; i >= 1; --i)
        tree[i] = max(tree[i*2], tree[i*2+1]);

    for (int i = 0; i < n; ++i)
    {
        wyn = max(wyn, tree[1] + ile_dod);
        int val = liczby[i];

        if (wystapienia_wsk[val] == wystapienia[val].size())
            wystapienia_wsk[val] = 0;

        if (wystapienia_wsk[val] + 1 == wystapienia[val].size())
            ile_dod += -koszty[val];
        else if (wystapienia_wsk[val] + 2 == wystapienia[val].size())
        {
            ile_dod += -koszty[val];
            dod_update = 2 * koszty[val];
            l_zap = wystapienia[val][wystapienia_wsk[val]+1]+1;
            update(1,base,1);
        }
        else
        {
            ile_dod += -koszty[val];

            dod_update = 2 * koszty[val];
            l_zap = wystapienia[val][wystapienia_wsk[val]+1]+1;
            update(1,base,1);

            dod_update = -koszty[val];
            l_zap = wystapienia[val][wystapienia_wsk[val]+2]+1;
            update(1,base,1);
        }
        wystapienia_wsk[val]++;
    }

    cout << wyn << '\n';

    return 0;
}

 

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 238 wizyt
pytanie zadane 3 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...