Zadanie kopiec eliminacje do ejoi, po 14 OIJ

Question

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!

Comments

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.

Answer 1

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.

Comments

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;
}