oj.uz

Submission #642851

# Submission time Handle Problem Language Result Execution time Memory
642851 2022-09-20T15:50:01 Z rilakkuma Fountain (eJOI20_fountain) C++14
100 / 100
 525 ms 43704 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};
  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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 3008 KB Output is correct
5 Correct 5 ms 3028 KB Output is correct
6 Correct 5 ms 3028 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 41320 KB Output is correct
2 Correct 384 ms 38372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 3008 KB Output is correct
5 Correct 5 ms 3028 KB Output is correct
6 Correct 5 ms 3028 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 348 ms 41320 KB Output is correct
9 Correct 384 ms 38372 KB Output is correct
10 Correct 6 ms 2900 KB Output is correct
11 Correct 231 ms 21956 KB Output is correct
12 Correct 525 ms 43704 KB Output is correct
13 Correct 461 ms 37648 KB Output is correct
14 Correct 382 ms 36440 KB Output is correct
15 Correct 331 ms 36288 KB Output is correct