oj.uz

Submission #642817

# Submission time Handle Problem Language Result Execution time Memory
642817 2022-09-20T15:04:36 Z rilakkuma Fountain (eJOI20_fountain) C++14
0 / 100
 257 ms 40568 KB 
# 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};
  for(int i=1; i<=n; i++){
    while(!stack.empty() && bowl[stack.back()].diameter < bowl[i].diameter){
      up[stack.back()][0] = i;
      stack.pop_back();
    }
    stack.push_back(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];
        break;
      }
    }

    cout << u << "\n";
  }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 257 ms 40568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -