Submission #1308765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308765		Johan	Fountain (eJOI20_fountain)	C++20	100 / 100	1004 ms	22592 KiB

fountain

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 6;
const int LG = 25;
int d[N], c[N], dpt[N], pr[N], st[N * 4], up[N][LG];
vector < int > adj[N];
void build(int v, int l, int r){
  if(l == r){
    st[v] = d[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  st[v] = max(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
  if(l > qr || r < ql)return -1e9;
  if(l >= ql && r <= qr)return st[v];
  int mid = (l + r) >> 1;
  return max(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
void dfs(int u, int pa){
  if(pa != -1){
    up[u][0] = pa;
    for(int i = 1; i < LG; i++)
      up[u][i] = up[up[u][i - 1]][i - 1];
    dpt[u] = dpt[pa] + 1;
    pr[u] = pr[pa] + c[u];
  }
  for(auto v : adj[u])
    dfs(v, u);
}
int up_k(int u, int k){
  for(int i = 0; i < LG; i++){
    if(k & (1 << i))
      u = up[u][i];
  }
  return u;
}
int main(){
  // #ifndef ONLINE_JUDGE
  //   freopen("input.txt", "r", stdin);
  //   freopen("output.txt", "w", stdout);
  // #endif
  int n, q;
  cin >> n >> q;
  for(int i = 1; i <= n; i++)
    cin >> d[i] >> c[i];
  build(1, 1, n);
  for(int i = 1; i <= n; i++){
    int l = i, r = n;
    int best = 0;
    while(r >= l){
      int mid = (l + r) >> 1;
      if(ask(1, 1, n, i, mid) > d[i]){
        r = mid - 1;
        best = mid;
      }
      else l = mid + 1;
    }
    adj[best].push_back(i);
  }
  dfs(0, -1);
  while(q--){
    int u, x;
    cin >> u >> x;
    if(pr[u] < x){
      cout << 0 << endl;
      continue;
    }
    int l = 0, r = dpt[u];
    int best = -1;
    while(r >= l){
      int mid = (l + r) >> 1;
      int nd = up_k(u, mid + 1);
      // cout << mid << ' ' << nd << endl;
      if(pr[u] - pr[nd] >= x){
        r = mid - 1;
        best = mid;
      }
      else l = mid + 1;
    }
    cout << up_k(u, best) << endl;
  }
}

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