oj.uz

Submission #642850

# Submission time Handle Problem Language Result Execution time Memory
642850 2022-09-20T15:47:31 Z rilakkuma Fountain (eJOI20_fountain) C++14
100 / 100
 554 ms 33748 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];
      }
    }
    if(u == n+1) u = 0;
    cout << u << "\n";
  }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 31716 KB Output is correct
2 Correct 398 ms 29380 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 382 ms 31716 KB Output is correct
9 Correct 398 ms 29380 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 197 ms 18428 KB Output is correct
12 Correct 554 ms 33748 KB Output is correct
13 Correct 445 ms 33136 KB Output is correct
14 Correct 381 ms 32712 KB Output is correct
15 Correct 381 ms 32688 KB Output is correct