Submission #753060

#	Time	Username	Problem	Language	Result	Execution time	Memory
753060		emad234	Fountain (eJOI20_fountain)	C++17	60 / 100	358 ms	53076 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40