oj.uz

Submission #642841

# Submission time Handle Problem Language Result Execution time Memory
642841 2022-09-20T15:37:58 Z rilakkuma Fountain (eJOI20_fountain) C++14
0 / 100
 257 ms 31688 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 = 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;
    sum[i][0] = 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;
    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=LOG-1; d>=0; d--){
      if(sum[u][d] < rem){
        rem -= sum[u][d];
        u = up[u][d];
        break;
      }
    }
    if(u == n+1) u = 0;
    cout << u << "\n";
  }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 468 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 31688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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