Submission #642851

#	Time	Username	Problem	Language	Result	Execution time	Memory
642851		rilakkuma	Fountain (eJOI20_fountain)	C++14	100 / 100	525 ms	43704 KiB

fountain

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
# define int long long
# define For(i, n) for(int i=0; i<n; i++)
# define Fori(i, n) for(int i=1; i<=n; i++)
# define Each(x, v) for(auto x : v)
 
struct Bowl {
  int diameter, volume;
};
 
const int LOG = 18;
int up[100005][LOG];
vector<int> g[100005];
int sum[100005][LOG];
Bowl bowl[100005];
 
void dfs(int u, int p = 0){
  for(int v: g[u]){
    if(v == p) continue;
    sum[v][0] = bowl[v].volume;
    for(int d=1; d<LOG; d++){
      up[v][d] = up[up[v][d-1]][d-1];
      sum[v][d] = sum[v][d-1] + sum[up[v][d-1]][d-1];
    }
    dfs(v, u);
  }
}
 
signed main(){
  ios_base :: sync_with_stdio(false); 
  int n, q;
  cin >> n >> q;
  bowl[0] = {1<<30, 0};
  for(int i=1; i<=n; i++){
    cin >> bowl[i].diameter >> bowl[i].volume;
  } 
 
  vector<int> stack = {0};
  int nxt[n+1];
  memset(nxt, 0, sizeof(nxt));
  for(int i=1; i<=n; i++){
    while(!stack.empty() && bowl[stack.back()].diameter < bowl[i].diameter){
      nxt[stack.back()] = i;
      stack.pop_back();
    }
    stack.push_back(i);
  } 
 
  for(int i=1; i<=n; i++){
    up[i][0] = nxt[i];
  }
 
  for(int i=1; i<=n; i++){
    g[up[i][0]].push_back(i);
  }
  dfs(0, 0);
 
  while(q--){
    int u, rem; cin >> u >> rem;
 
    for(int d=LOG-1; d>=0; d--){
      if(sum[u][d] < rem){
        rem -= sum[u][d];
        u = up[u][d];
      }
    }
 
    cout << u << "\n";
  }
}

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