oj.uz

Submission #642845

# Submission time Handle Problem Language Result Execution time Memory
642845 2022-09-20T15:45:09 Z rilakkuma Fountain (eJOI20_fountain) C++14
100 / 100
 552 ms 33700 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;
  } 

  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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 31644 KB Output is correct
2 Correct 380 ms 29380 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 358 ms 31644 KB Output is correct
9 Correct 380 ms 29380 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 213 ms 18428 KB Output is correct
12 Correct 552 ms 33700 KB Output is correct
13 Correct 453 ms 33144 KB Output is correct
14 Correct 383 ms 32772 KB Output is correct
15 Correct 370 ms 32748 KB Output is correct