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

Zadanie kopiec eliminacje do ejoi, po 14 OIJ

Object Storage Arubacloud
0 głosów
186 wizyt
pytanie zadane 16 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam problem z takim zdaniem: https://szkopul.edu.pl/problemset/problem/imOmSmDfdk-dlL7rD_ggN1ji/site/?key=statement

Łatwo zrobiłem pierwsze 2 podzadania (N,Q <= 1000), (x = y) wsumie dostałem 42pkt. Nie wiem co dalej, podejrzewam, że wejdzie tu jakaś sztuczka offline, ale nie mam pomysłu. Prosiłbym o hinta.

Z góry dziękuję za pomoc i poświęcony czas!
komentarz 16 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Jedyne spostrzerzenie mialem takie, ze róznica między wartoscia rodzica a dziecka musi być <= 0, wiec myslalem zeby zrobic jakiegos przedziałowca, ale nie wiem czy to coś daje.

1 odpowiedź

0 głosów
odpowiedź 17 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Już chyba mam. Na krawędzi zapisujemy Child-ojciec. Robimy drzewo przedzialowe przedział-przedział. Dodaj na przedziale, min odczyujemy w korzeniu(na całym przedziale). Przy update dodajemy na krawędziach.
komentarz 17 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Nawet taki krótki kod z drzewem przedział-przedział dostaje ac.

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int n = 0, q = 0, l = 0, p = 0, val = 0, base = (1 << 19), rozmiar_drzewa = base * 2;
vector<int> A;
vector<ll> tree;
vector<ll> tree2;

inline void preprocesing()
{
    tree.assign(rozmiar_drzewa,1e18+50);
    tree2.assign(rozmiar_drzewa,0);
    for (int i = 2; i <= n; ++i)
        tree[i-1+base] = A[i] - A[i/2];
    for (int i = base-1; i >= 1; --i)
        tree[i] = min(tree[i*2],tree[i*2+1]);
}

inline void sprawdzaj()
{
    if (tree[1] >= 0)
        cout << "TAK" << '\n';
    else
        cout << "NIE" << '\n';
}

inline void dodaj(int l_zap, int p_zap, int l_kontrolowana, int p_kontrolowana, int v, int val)
{
    if (l_kontrolowana > p_zap or p_kontrolowana < l_zap)
        return;
    else if (l_kontrolowana >= l_zap and p_kontrolowana <= p_zap)
    {
        tree[v] += val;
        tree2[v] += val;
    }
    else
    {
        tree[v*2] += tree2[v];
        tree[v*2+1] += tree2[v];
        tree2[v*2] += tree2[v];
        tree2[v*2+1] += tree2[v];
        tree2[v] = 0;
        int srod = (p_kontrolowana - l_kontrolowana + 1) / 2;
        dodaj(l_zap,p_zap,l_kontrolowana,l_kontrolowana + srod - 1,v*2,val);
        dodaj(l_zap,p_zap,l_kontrolowana + srod,p_kontrolowana,v*2+1,val);
        tree[v] = min(tree[v*2],tree[v*2+1]);
    }
}

inline void update()
{
    cin >> l >> p >> val;
    dodaj(l-1,p-1,0,base-1,1,val);
    dodaj(min(base,l*2-1),min(base,p*2),0,base-1,1,-val);
}

inline void wypisz_drzewo()
{
    for (int i = 1; i < rozmiar_drzewa; ++i)
        cout << tree[i] << " ";
    cout << endl;
}

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

    cin >> n;

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

    preprocesing();
    sprawdzaj();

    cin >> q;
    while(q--)
    {
        update();
        sprawdzaj();
    }

    return 0;
}

 

Podobne pytania

0 głosów
1 odpowiedź 152 wizyt
0 głosów
1 odpowiedź 111 wizyt
pytanie zadane 16 czerwca 2023 w Algorytmy przez nerfiko Nowicjusz (170 p.)
0 głosów
1 odpowiedź 157 wizyt
pytanie zadane 24 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,539 zapytań

141,381 odpowiedzi

319,469 komentarzy

61,926 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy 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!

...