Submission #1035410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035410		juicy	Fountain (eJOI20_fountain)	C++17	100 / 100	96 ms	11348 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, q;
  cin >> n >> q;
  vector<int> d(n), c(n);
  for (int i = 0; i < n; ++i) {
    cin >> d[i] >> c[i];
  }
  vector<int> res(q);
  vector<array<int, 3>> Queries;
  for (int i = 0; i < q; ++i) {
    int u, v; cin >> u >> v; --u;
    Queries.push_back({u, v, i});
  }
  sort(Queries.rbegin(), Queries.rend());
  vector<array<int, 2>> st;
  auto solve = [&](int x) {
    int l = 1, r = st.size() - 1, p = 0;
    while (l <= r) {
      int md = (l + r) / 2;
      if (st.back()[1] - st[md - 1][1] >= x) {
        p = st[md][0] + 1;
        l = md + 1;
      } else {
        r = md - 1;
      }
    }
    return p;
  };
  st.push_back({n, 0});
  for (int i = n - 1, j = 0; i >= 0; --i) {
    while (st.size() > 1 && d[st.back()[0]] <= d[i]) {
      st.pop_back();
    }
    st.push_back({i, st.back()[1] + c[i]});
    while (j < q && Queries[j][0] == i) {
      res[Queries[j][2]] = solve(Queries[j][1]);
      ++j;
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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