Submission #642845

#	Time	Username	Problem	Language	Result	Execution time	Memory
642845		rilakkuma	Fountain (eJOI20_fountain)	C++14	100 / 100	552 ms	33700 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 = 19;
int up[100005][LOG];
int sum[100005][LOG];
Bowl bowl[100005];

signed main(){
  ios_base :: sync_with_stdio(false); 
  int n, q;
  cin >> n >> q;
  for(int i=1; i<=n; i++){
    cin >> bowl[i].diameter >> bowl[i].volume;
  } 

  vector<int> stack;
  for(int i=n; i>=1; i--){
    while(!stack.empty() && bowl[stack.back()].diameter <= bowl[i].diameter) 
      stack.pop_back();
    
    if(!stack.empty()) up[i][0] = stack.back();
    else up[i][0] = n+1;
    sum[i][0] = bowl[i].volume;
    stack.push_back(i);
  }

  sum[n+1][0] = 1e18;
  for(int d=1; d<LOG; d++){
    sum[n+1][d] = 1e18;
    for(int v=1; v<=n; v++){
      up[v][d] = up[up[v][d-1]][d-1];
      sum[v][d] = sum[v][d-1] + sum[up[v][d-1]][d-1];
    }
  }

  while(q--){
    int u, rem; cin >> u >> rem;
    for(int d=18; d>=0; d--) {
      if(sum[u][d] < rem) {
        rem -= sum[u][d];
        u = up[u][d];
      }
    }
    if(u == n+1) u = 0;
    cout << u << "\n";
  }
}

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