Submission #811449

#	Time	Username	Problem	Language	Result	Execution time	Memory
811449		taher	Fountain (eJOI20_fountain)	C++17	100 / 100	122 ms	13716 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;

  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
  }

  vector<vector<int>> at(n);
  vector<array<int, 2>> qe(q);
  for (int i = 0; i < q; i++) {
    cin >> qe[i][0] >> qe[i][1];
    --qe[i][0];
    at[qe[i][0]].push_back(i);
  }

  vector<int> stk;
  vector<int> pref;

  auto get = [&](int v) {
    int len = (int) pref.size();
    int low = 0, high = len - 1;

    if (pref.back() < v) {
      return 0;
    }

    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (pref.back() - (mid > 0 ? pref[mid - 1] : 0) < v) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    --low;

    return stk[low] + 1;
  };

  vector<int> res(q);
  for (int i = n - 1; i >= 0; i--) {
    while (!stk.empty() && a[stk.back()][0] <= a[i][0]) {
      stk.pop_back();
      pref.pop_back();
    }

    int x = (pref.empty() ? 0 : pref.back());
    pref.push_back(x + a[i][1]);
    stk.push_back(i);

    for (auto query_id : at[i]) {
      int v = qe[query_id][1];
      res[query_id] = get(v);
    }
  }

  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