oj.uz

Submission #753061

# Submission time Handle Problem Language Result Execution time Memory
753061 2023-06-04T14:06:22 Z emad234 Fountain (eJOI20_fountain) C++17
100 / 100
 363 ms 58044 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e5 + 3;
pair<ll,ll> a[mxN];
pair<ll,ll> st[mxN][32];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  ll n,t;
  cin >>n>>t;
  for(ll i = 0;i < n;i++){
    cin >>a[i].first>>a[i].second;
  }
  a[n] = {1e8,1e8};
  n++;
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
  for(ll i = 0;i < n;i++){
    while(q.size() && a[i].first > q.top().first){
      st[q.top().second][0] = {a[i].second,i};
      // cout<<q.top().second<<' '<<q.top().first<<' '<<i<<'\n';
      q.pop();
    }
    q.push({a[i].first,i});
  }
  st[n][0] = {1e8,n};
  for(ll k = 1;k < 32;k++){
    for(ll i = 0;i < n;i++){
      st[i][k] = {st[st[i][k - 1].second][k - 1].first + st[i][k - 1].first,st[st[i][k - 1].second][k - 1].second};
    }
  }
  while(t--){
    ll p,c;
    cin >>p>>c;
    // cout<<'\n';
    p--;
    c -= a[p].second;
    for(ll k = 31;k >= 0;k--){
      if(st[p][k].first < c){
        // cout<<p<<' '<<st[p][k].second<<' '<<c<<'\n';
        c -= st[p][k].first;
        p = st[p][k].second;
      }
    }
    if(c > 0)
      p = st[p][0].second;
    if(p == n - 1) p = -1;
    cout<<p + 1<<'\n';
  }
}































//                                                                  nice

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 50272 KB Output is correct
2 Correct 282 ms 46288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 261 ms 50272 KB Output is correct
9 Correct 282 ms 46288 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 130 ms 29692 KB Output is correct
12 Correct 363 ms 53152 KB Output is correct
13 Correct 307 ms 53432 KB Output is correct
14 Correct 174 ms 56124 KB Output is correct
15 Correct 158 ms 58044 KB Output is correct