Submission #1310533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310533		tuncay_pasha	Fountain (eJOI20_fountain)	C++20	100 / 100	373 ms	30184 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int LG = 21;

vector<int> adj[N];
int V[N], D[N];
int up[N][LG], sum[N][LG];
int dist[N];
int in[N], out[N], tmr;

void dfs(int u, int p) {
  in[u] = ++tmr;
  up[u][0] = p;
  sum[u][0] = V[p];
  for (int i = 1; i < LG; ++i) {
    up[u][i] = up[up[u][i - 1]][i - 1];
    int mid = up[u][i - 1];
    if (mid == 0) {
      sum[u][i] = sum[u][i - 1];
    }
    else sum[u][i] = sum[u][i - 1] + sum[mid][i - 1];
  }
  for (int &v : adj[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
  out[u] = tmr;
}
int get(int u, int k) {
  if (V[u] >= k) return u;
  int cur = V[u];
  for (int i = LG - 1; i >= 0; --i) {
    if (cur + sum[u][i] < k) {
      cur += sum[u][i];
      u = up[u][i];
    }
  }
  return up[u][0];
}
void _() {
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> D[i] >> V[i];
  }
  stack<int> st;
  for (int i = n; i >= 1; --i) {
    while (!st.empty() && D[st.top()] <= D[i]) {
      st.pop();
    }
    int p = (st.empty() ? 0 : st.top());
    adj[p].push_back(i);
    st.push(i);
  }
  dfs(0, 0);
  while (q--) {
    int u, k;
    cin >> u >> k;
    cout << get(u, k) << '\n';
  }
}

signed main() {
  _();
  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40