Submission #813622

#	Time	Username	Problem	Language	Result	Execution time	Memory
813622		kostka	Fountain (eJOI20_fountain)	C++14	100 / 100	470 ms	16428 KiB

fountain

#include "bits/stdc++.h"

using namespace std;

struct Zbiornik
{
  int D, C;
  int nastepny_wiekszy_zbiornik = 0;
};

const int LOGN = 17;
int N, Q;
vector<Zbiornik> zbiorniki;

// Ta funkcja generuje krawędzie od każdego zbiornika do następnego zbiornika,
// który ma średnicę ściśle większą od naszej, znajdującego się poniżej nas.
void ObliczKrawedzie()
{
  stack<int> S;
  for (int i = 1; i <= N; i++)
  {
    // Jeśli na stosie jest zbiornik mniejszy od nas,
    // to zdejmujemy go ze stosu i ustawiamy krawędź do zbiornika,
    // który aktualnie rozważamy.
    while (!S.empty() and zbiorniki[S.top()].D < zbiorniki[i].D)
    {
      int s = S.top();
      S.pop();
      zbiorniki[s].nastepny_wiekszy_zbiornik = i;
    }
    // Na końcu, po prostu odkładamy aktualny zbiornik na stos.
    S.push(i);
  }
}

// Wskaźniki pominięcia będą przechowywać dwie wartości: cel i łączna pojemność
// wszystkich zbiorników, do których można dotrzeć wykonując 2^i kroków
// dla każdego i.
struct SkipPointer
{
  int cel = 0, calkowita_pojemnosc;
};

vector<vector<SkipPointer>> skip_pointers;

void ObliczSkipPointery()
{
  skip_pointers.resize(LOGN);
  skip_pointers[0].resize(N+1);
  // Tutaj ustawiamy pierwszy poziom skip pointerow.
  // Wykorzystujemy krawędzie, które obliczyliśmy we wcześniejszym kroku,
  // aby ustawić następny cel (osiągalny za pomocą 2^0 kroków),
  // a łączna pojemność to po prostu pojemność tego zbiornika.
  for (int i = 0; i < N; i++)
  {
    skip_pointers[0][i].cel = zbiorniki[i].nastepny_wiekszy_zbiornik;
    skip_pointers[0][i].calkowita_pojemnosc = zbiorniki[i].C;
  }
  // Teraz dla każdego poziomu obliczamy odpowiednie skip pointery.
  for (int log = 1; log < LOGN; log++)
  {
    skip_pointers[log].resize(zbiorniki.size());
    for (int i = 1; i <= N; i++)
    {
      // Tutaj pobieramy cel z poziomu (log-1),
      // czyli osiągalny za pomocą 2^(log-1) kroków.
      int poprzedni_cel = skip_pointers[log - 1][i].cel;
      // Jeśli jest równy 0, to oznacza, że nie możemy iść dalej,
      // więc po prostu zachowujemy cel (domyślnie będzie równy -1),
      // i przypisujemy poprzednią łączną pojemność do tego skip pointera.
      if (poprzedni_cel == 0)
      {
        skip_pointers[log][i].calkowita_pojemnosc = \
          skip_pointers[log - 1][i].calkowita_pojemnosc;
      }
      // W przeciwnym razie aktualizujemy cel, idąc dalej o 2^(log-1) kroków,
      // (czyli łącznie używamy 2^(log-1) + 2^(log-1) = 2^log kroków),
      // a łączna pojemność wszystkich zbiorników po drodze do celu
      // jest równa sumie tych dwóch wykorzystanych skip pointerow.
      else
      {
        skip_pointers[log][i].cel = \
          skip_pointers[log - 1][poprzedni_cel].cel;
        skip_pointers[log][i].calkowita_pojemnosc = \
          skip_pointers[log - 1][i].calkowita_pojemnosc + \
          skip_pointers[log - 1][poprzedni_cel].calkowita_pojemnosc;
      }
    }
  }
}

void ObsluzZapytania()
{
  for (int i = 0; i < Q; i++)
  {
    int R, V;
    cin >> R >> V;
    // Tutaj dla każdego zapytania, idziemy od największego skip pointera,
    // który wcześniej obliczyliśmy, i sprawdzamy, czy możemy go użyć, czyli
    // ilość wody, którą mamy, jest większa niż łączna pojemność
    // tego skip pointera.
    for (int log = LOGN - 1; log >= 0; log--)
    {
      // Jeśli już jesteśmy na dole, nie rób nic.
      if (R == 0) continue;
      // W przeciwnym razie, jeśli powinniśmy użyć aktualnie rozwazany skip 
      // pointer, przesuwamy R (zbiornik, w którym aktualnie się znajdujemy)
      // i zmniejszamy ilość wody o łączną pojemność wszystkich zbiorników,
      // które wykorzystaliśmy.
      if (skip_pointers[log][R].calkowita_pojemnosc < V)
      {
        V -= skip_pointers[log][R].calkowita_pojemnosc;
        R = skip_pointers[log][R].cel;
      }
    }
    cout << R << "\n";
  }
}

int main()
{
  cin >> N >> Q;
  zbiorniki.resize(N+1);
  for (int i = 1; i <= N; i++)
  {
    cin >> zbiorniki[i].D >> zbiorniki[i].C;
  }
  ObliczKrawedzie();
  ObliczSkipPointery();
  ObsluzZapytania();
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40