oj.uz

답안 #963759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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