Submission #813451

#	Time	Username	Problem	Language	Result	Execution time	Memory
813451		kostka	Fountain (eJOI20_fountain)	C++14	100 / 100	200 ms	17160 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40