Submission #813430

#	Time	Username	Problem	Language	Result	Execution time	Memory
813430		kostka	Fountain (eJOI20_fountain)	C++14	100 / 100	173 ms	20072 KiB

fountain

#include "bits/stdc++.h"

using namespace std;

struct reservoir
{
  int D, C;
  int next_larger_reservoir = -1;
};

const int LOG = 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 = 0; 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);
  }
  // for (int i = 0; i < N; i++)
  // {
  //   cerr << i << ": " << reservoirs[i].next_larger_reservoir << "\n";
  // }
}

struct SkipPointer
{
  int destination = -1, total_capacity;
};

vector<vector<SkipPointer>> skip_pointers;

void CalculateSkipPointers()
{
  skip_pointers.resize(LOG);
  skip_pointers[0].resize(N);
  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;
  }
  for (int log = 1; log < LOG; log++)
  {
    skip_pointers[log].resize(reservoirs.size());
    for (int i = 0; i < N; i++)
    {
      int previous_destination = skip_pointers[log - 1][i].destination;
      if (previous_destination == -1)
      {
        skip_pointers[log][i].total_capacity = skip_pointers[log - 1][i].total_capacity;
      }
      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;
      }
    }
  }
  // for (int i=0; i<N; i++) {
  //   cerr << i << ": " << skip_pointers[2][i].destination << " " << skip_pointers[2][i].total_capacity << "\n";
  // }
}

void HandleQueries()
{
  for (int i = 0; i < Q; i++)
  {
    int R, V;
    cin >> R >> V;
    R--;
    for (int log = LOG - 1; log >= 0; log--)
    {
      // cerr << "level " << log << "\n";
      // cerr << "R" << R << " " << "V" << V << "\n";
      // cerr << skip_pointers[log][R].total_capacity << "\n";
      if (R != -1 and skip_pointers[log][R].total_capacity < V)
      {
        V -= skip_pointers[log][R].total_capacity;
        R = skip_pointers[log][R].destination;
      }
    }
    cout << R + 1 << "\n";
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  reservoirs.resize(N);
  for (int i = 0; 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