oj.uz

Submission #637990

# Submission time Handle Problem Language Result Execution time Memory
637990 2022-09-04T02:47:17 Z devariaota Fountain (eJOI20_fountain) C++17
100 / 100
 394 ms 63828 KB 
#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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 58976 KB Output is correct
2 Correct 306 ms 54784 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 728 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 283 ms 58976 KB Output is correct
9 Correct 306 ms 54784 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 135 ms 34936 KB Output is correct
12 Correct 394 ms 63828 KB Output is correct
13 Correct 329 ms 63436 KB Output is correct
14 Correct 236 ms 62796 KB Output is correct
15 Correct 179 ms 63180 KB Output is correct