oj.uz

Submission #753060

# Submission time Handle Problem Language Result Execution time Memory
753060 2023-06-04T14:05:22 Z emad234 Fountain (eJOI20_fountain) C++17
60 / 100
 358 ms 53076 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] = {1e10,1e10};
  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] = {1e10,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 0 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 1 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 251 ms 50220 KB Output is correct
2 Correct 255 ms 46328 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 251 ms 50220 KB Output is correct
9 Correct 255 ms 46328 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 141 ms 29696 KB Output is correct
12 Correct 358 ms 53076 KB Output is correct
13 Incorrect 177 ms 52656 KB Output isn't correct
14 Halted 0 ms 0 KB -