oj.uz

답안 #813621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813621 2023-08-08T00:45:29 Z kostka Fountain (eJOI20_fountain) C++14
100 / 100
 132 ms 16460 KB 
#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()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 464 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 14812 KB Output is correct
2 Correct 98 ms 13848 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 87 ms 14812 KB Output is correct
9 Correct 98 ms 13848 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 46 ms 8964 KB Output is correct
12 Correct 132 ms 16040 KB Output is correct
13 Correct 112 ms 16076 KB Output is correct
14 Correct 86 ms 15996 KB Output is correct
15 Correct 83 ms 16460 KB Output is correct