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!