oj.uz

Submission #813430

# Submission time Handle Problem Language Result Execution time Memory
813430 2023-08-07T17:52:32 Z kostka Fountain (eJOI20_fountain) C++14
100 / 100
 173 ms 20072 KB 
#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.0 / 30.0

# Verdict Execution time Memory 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 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 17652 KB Output is correct
2 Correct 102 ms 16844 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory 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 468 KB Output is correct
8 Correct 106 ms 17652 KB Output is correct
9 Correct 102 ms 16844 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 47 ms 10564 KB Output is correct
12 Correct 173 ms 20072 KB Output is correct
13 Correct 110 ms 19792 KB Output is correct
14 Correct 86 ms 18844 KB Output is correct
15 Correct 114 ms 19608 KB Output is correct