Submission #1150612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150612		fryingduc	Fountain (eJOI20_fountain)	C++20	100 / 100	267 ms	26632 KiB

fountain

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int LG = 19;
int n, q;
int a[maxn];
long long c[maxn];
int up[maxn][LG + 1];
long long sum[maxn][LG + 1];

void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> c[i];
  }
  stack<int> st;
  c[0] = 2e9;
  for (int i = n; i; --i) {
    while (!st.empty() and a[st.top()] <= a[i]) {
      st.pop();
    }
    if (!st.empty()) {
      up[i][0] = st.top();
    }
    st.push(i);
    sum[i][0] = c[up[i][0]];
  }
  for (int i = 1; i <= LG; ++i) {
    for (int u = 1; u <= n; ++u) {
      up[u][i] = up[up[u][i - 1]][i - 1];
      sum[u][i] = sum[u][i - 1] + sum[up[u][i - 1]][i - 1];
    }
  }
  while (q--) {
    int u, r; cin >> u >> r;
    long long cap = c[u];
    if (cap >= r) {
      cout << u << '\n';
      continue;
    }
    for (int i = LG; i >= 0; --i) {
      if (cap + sum[u][i] < r) {
        cap += sum[u][i];
        u = up[u][i];
      }
    }
//    debug(cap);
    cout << up[u][0] << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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