oj.uz

Submission #642849

# Submission time Handle Problem Language Result Execution time Memory
642849 2022-09-20T15:47:12 Z rilakkuma Fountain (eJOI20_fountain) C++14
100 / 100
 562 ms 33808 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=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 340 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 3 ms 596 KB Output is correct
6 Correct 3 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 368 ms 31648 KB Output is correct
2 Correct 412 ms 29508 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 368 ms 31648 KB Output is correct
9 Correct 412 ms 29508 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 207 ms 18368 KB Output is correct
12 Correct 562 ms 33808 KB Output is correct
13 Correct 513 ms 33100 KB Output is correct
14 Correct 395 ms 32784 KB Output is correct
15 Correct 356 ms 32768 KB Output is correct