제출 #1310532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310532		tuncay_pasha	Fountain (eJOI20_fountain)	C++20	0 / 100	253 ms	27784 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[u] + 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] - V[mid];
  }
  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 = 0;
  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];
  }
  for (int i = 1; i <= n; ++i) {
    int idx = 0;
    for (int j = i + 1; j <= n; ++j) {
      if (D[j] > D[i]) {
        idx = j;
        break;
      }
    }
    adj[idx].push_back(i);
  }
  dfs(0, 0);
  while (q--) {
    int u, k;
    cin >> u >> k;
    cout << get(u, k) << '\n';
  }
}

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

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