oj.uz

Submission #963759

# Submission time Handle Problem Language Result Execution time Memory
963759 2024-04-15T15:40:02 Z Trisanu_Das Fountain (eJOI20_fountain) C++17
100 / 100
 303 ms 37684 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
 
int n, q, jump[100005][20], h2o[100005][20];
 
signed main(){
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  cin >> n >> q;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  for(int i = 1; i <= n; i++){
    int d; cin >> d >> h2o[i][0];
    while(!pq.empty() && pq.top().ff < d){
      jump[pq.top().ss][0] = i;
      pq.pop();
    }
    pq.push({d, i});
  }
  while(!pq.empty()){
    jump[pq.top().ss][0] = 0;
    pq.pop();
  }
  jump[0][0] = 0; h2o[0][0] = 0;
  for(int j = 1; j < 20; j++)
    for(int i = 0; i <= n; i++){
      jump[i][j] = jump[jump[i][j - 1]][j - 1];
      h2o[i][j] = h2o[i][j - 1] + h2o[jump[i][j - 1]][j - 1];
    }
  
  while(q--){
    int r, v; cin >> r >> v;
    for(int i = 19; i >= 0; i--){
      if(h2o[r][i] >= v) continue;
      v -= h2o[r][i];
      r = jump[r][i];
    }
    cout << r << '\n';
  }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 31724 KB Output is correct
2 Correct 196 ms 33228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 199 ms 31724 KB Output is correct
9 Correct 196 ms 33228 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 60 ms 21324 KB Output is correct
12 Correct 303 ms 36944 KB Output is correct
13 Correct 188 ms 36824 KB Output is correct
14 Correct 132 ms 35852 KB Output is correct
15 Correct 105 ms 37684 KB Output is correct