oj.uz

Submission #642827

# Submission time Handle Problem Language Result Execution time Memory
642827 2022-09-20T15:25:29 Z rilakkuma Fountain (eJOI20_fountain) C++14
0 / 100
 241 ms 29260 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];
int sum[100005][LOG];
Bowl bowl[100005];

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;
    sum[i][0] = 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 d=1; d<LOG; d++){
    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;
      }
    }

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

Subtask #1
0 / 30.0

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