oj.uz

답안 #813451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813451 2023-08-07T18:03:35 Z kostka Fountain (eJOI20_fountain) C++14
100 / 100
 200 ms 17160 KB 
#include "bits/stdc++.h"

using namespace std;

struct reservoir
{
  int D, C;
  int next_larger_reservoir = 0;
};

const int LOGN = 17;
int N, Q;
vector<reservoir> reservoirs;

// This function generate edges from each reservoir to the
// next reservoir that is strictly larger in diamater
// below us.
void CalculateEdges()
{
  stack<int> S;
  for (int i = 1; i <= N; i++)
  {
    // If there is an reservoir on the stack that is smaller than us
    // then pop it from the stack and set it edge to the reservoir
    // that we are currently considering.
    while (!S.empty() and reservoirs[S.top()].D < reservoirs[i].D)
    {
      int s = S.top();
      S.pop();
      reservoirs[s].next_larger_reservoir = i;
    }
    // At the end, just push the current reservoir on the stack.
    S.push(i);
  }
}

// The skip pointers will keep two values, the destination and total capacity
// of all of the reservoirs that can be reached using 2^i steps for each i.
struct SkipPointer
{
  int destination = 0, total_capacity;
};

vector<vector<SkipPointer>> skip_pointers;

void CalculateSkipPointers()
{
  skip_pointers.resize(LOGN);
  skip_pointers[0].resize(N+1);
  // Here we are setting the first level of skip pointers.
  // We use the edges we calculated in the previous step to set the 
  // next destination (reachable by using 2^0 steps),
  // and total capacity is just the capacity of this reservoir.
  for (int i = 0; i < N; i++)
  {
    skip_pointers[0][i].destination = reservoirs[i].next_larger_reservoir;
    skip_pointers[0][i].total_capacity = reservoirs[i].C;
  }
  // Now for each level, we calculate the corresponding skip pointers.
  for (int log = 1; log < LOGN; log++)
  {
    skip_pointers[log].resize(reservoirs.size());
    for (int i = 1; i <= N; i++)
    {
      // Here we take the destination from the (log-1) level,
      // i.e. that is reachable by using 2^(log-1) steps.
      int previous_destination = skip_pointers[log - 1][i].destination;
      // If it is equal to 0, that means that we cannot go any further,
      // so we just keep the destination (will be equal to -1 by default),
      // and we just assign the previous total capacit to this skip pointer.
      if (previous_destination == 0)
      {
        skip_pointers[log][i].total_capacity = skip_pointers[log - 1][i].total_capacity;
      }
      // Otherwise, we update the destination, by going next 2^(log-1) steps,
      // (so we use 2^(log-1) + 2^(log-1) = 2^log steps in total),
      // and the total_capacity of all the reservoirs on the way to the 
      // destination is equal to the sum of these two skip pointers that we used
      // to get here.
      else
      {
        skip_pointers[log][i].destination = \
          skip_pointers[log - 1][previous_destination].destination;
        skip_pointers[log][i].total_capacity = \
          skip_pointers[log - 1][i].total_capacity + \
          skip_pointers[log - 1][previous_destination].total_capacity;
      }
    }
  }
}

void HandleQueries()
{
  for (int i = 0; i < Q; i++)
  {
    int R, V;
    cin >> R >> V;
    // Here for every query, we go from the largest skip pointer
    // that we precalculated and see if we can use it, i.e.
    // the amount of water we have is larger that the total capacity
    // of this skip pointer.
    for (int log = LOGN - 1; log >= 0; log--)
    {
      // If we are already at the bottom, do nothing.
      if (R == 0) continue;
      // Otherwise, if we should this skip pointer,
      // move R (the reservoir that we are currently in)
      // and decrease the amount of water we have
      // by the total capacity of all the reservoir that we used.
      if (R != 0 and skip_pointers[log][R].total_capacity < V)
      {
        V -= skip_pointers[log][R].total_capacity;
        R = skip_pointers[log][R].destination;
      }
    }
    cout << R << "\n";
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  reservoirs.resize(N+1);
  for (int i = 1; i <= N; i++)
  {
    cin >> reservoirs[i].D >> reservoirs[i].C;
  }
  CalculateEdges();
  CalculateSkipPointers();
  HandleQueries();
}

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 468 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 15508 KB Output is correct
2 Correct 128 ms 14516 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 468 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 123 ms 15508 KB Output is correct
9 Correct 128 ms 14516 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 50 ms 9624 KB Output is correct
12 Correct 200 ms 16808 KB Output is correct
13 Correct 131 ms 16840 KB Output is correct
14 Correct 101 ms 16788 KB Output is correct
15 Correct 91 ms 17160 KB Output is correct