Submission #637990

#	Time	Username	Problem	Language	Result	Execution time	Memory
637990		devariaota	Fountain (eJOI20_fountain)	C++17	100 / 100	394 ms	63828 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
#define pb push_back
const ll nax = 1e5 + 5;
const ll inf = 1e13;

ll n, q;
ll d[nax], k[nax], seg[4*nax];
ll par[nax][35], pref[nax][35];

void built(ll l, ll r, ll pos){
  if(l == r){
    seg[pos] = d[l];
  }
  else{
    ll mid = (l + r) / 2;
    built(l, mid, 2*pos);
    built(mid + 1, r, 2*pos+1);
    seg[pos] = max(seg[2*pos], seg[2*pos+1]);
  }
}

void upd(ll l, ll r, ll pos, ll fp, ll val){
  if(l == fp && r == fp){
    seg[pos] = val;
  }
  else if(l > fp || r < fp){
    return;
  }
  else{
    ll mid = (l + r) / 2;
    upd(l, mid, 2*pos, fp, val);
    upd(mid + 1, r, 2*pos+1, fp, val);
    seg[pos] = max(seg[2*pos], seg[2*pos+1]);
  }
}

ll que(ll l, ll r, ll pos, ll val){
  if(l == r && d[l] > val){
    return l;
  }
  else if(l == r){
    return n + 1;
  }
  else{
    ll mid = (l + r) / 2;
    ll lf = seg[2*pos], rg = seg[2*pos+1];
    if(lf > val){
      return que(l, mid, 2*pos, val);
    }
    else if(rg > val){
      return que(mid + 1, r, 2*pos+1, val);
    }
    else{
      return n + 1;
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
  
  cin >> n >> q;
  for(ll i = 1; i <= n; i++){
    cin >> d[i] >> k[i];
  }
  built(1, n, 1);
  for(ll i = 1; i <= n; i++){
    upd(1, n, 1, i, 0);
    ll target = que(1, n, 1, d[i]);
    if(target == n + 1){
      par[i][0] = target, pref[i][0] = inf;
    }
    else{
      par[i][0] = target, pref[i][0] = k[target];
    }
  }
  for(ll j = 0; j < 30; j++){
    par[n+1][j] = n + 1, pref[n+1][j] = inf;
  }
  //cout << par[n+1][0] << '\n';
  for(ll j = 1; j < 30; j++){
    for(ll i = 1; i <= n; i++){
      ll bfr = par[i][j-1];
      pref[i][j] = pref[i][j-1] + pref[bfr][j-1];
      par[i][j] = par[bfr][j-1];
      //cout << par[i][j] << " " << bfr << " " << j - 1 << " " << par[bfr][j-1] << '\n';
    }
    //cout << '\n';
  }
  while(q--){
    ll x, y;
    cin >> x >> y;
    if(y <= k[x]){
      cout << x << '\n';
    }
    else{
      ll cur = x, ans = n + 1, sum = k[x];
      for(ll i = 29; i >= 0; i--){
        //cout << sum << " " << par[cur][i] << " " << pref << '\n';
        if(sum + pref[cur][i] >= y){
          ans = par[cur][i];
        }
        else{
          sum += pref[cur][i];
          cur = par[cur][i];
        }
      }
      if(ans == n + 1) ans = 0;
      cout << ans << '\n';
    }
  }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40