oj.uz

답안 #813617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813617 2023-08-08T00:39:54 Z kostka Fountain (eJOI20_fountain) C++14
100 / 100
 152 ms 19968 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 WskaznikPomijania
{
  int cel = 0, calkowita_pojemnosc;
};

vector<vector<WskaznikPomijania>> wskazniki_pomijania;

void ObliczWskaznikiPomijania()
{
  wskazniki_pomijania.resize(LOGN);
  wskazniki_pomijania[0].resize(N+1);
  // Tutaj ustawiamy pierwszy poziom wskazników pomijania.
  // 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++)
  {
    wskazniki_pomijania[0][i].cel = zbiorniki[i].nastepny_wiekszy_zbiornik;
    wskazniki_pomijania[0][i].calkowita_pojemnosc = zbiorniki[i].C;
  }
  // Teraz dla każdego poziomu obliczamy odpowiednie wskazniki pomijania.
  for (int log = 1; log < LOGN; log++)
  {
    wskazniki_pomijania[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 = wskazniki_pomijania[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 wskaznika pomijania.
      if (poprzedni_cel == 0)
      {
        wskazniki_pomijania[log][i].calkowita_pojemnosc = wskazniki_pomijania[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 wskazników pomijania.
      else
      {
        wskazniki_pomijania[log][i].cel = \
          wskazniki_pomijania[log - 1][poprzedni_cel].cel;
        wskazniki_pomijania[log][i].calkowita_pojemnosc = \
          wskazniki_pomijania[log - 1][i].calkowita_pojemnosc + \
          wskazniki_pomijania[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 wskaznika pomijania,
    // 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 wskaznika pomijania.
    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ć tego wskaznika pomijania,
      // przesuwamy R (zbiornik, w którym aktualnie się znajdujemy)
      // i zmniejszamy ilość wody o łączną pojemność wszystkich zbiorników,
      // które wykorzystaliśmy.
      if (R != 0 and wskazniki_pomijania[log][R].calkowita_pojemnosc < V)
      {
        V -= wskazniki_pomijania[log][R].calkowita_pojemnosc;
        R = wskazniki_pomijania[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();
  ObliczWskaznikiPomijania();
  ObsluzZapytania();
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 17712 KB Output is correct
2 Correct 104 ms 16996 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 107 ms 17712 KB Output is correct
9 Correct 104 ms 16996 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 47 ms 10564 KB Output is correct
12 Correct 152 ms 19968 KB Output is correct
13 Correct 125 ms 19676 KB Output is correct
14 Correct 90 ms 18900 KB Output is correct
15 Correct 88 ms 19680 KB Output is correct