Submission #1158901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158901		LinkedArray	Fountain (eJOI20_fountain)	C++20	30 / 100	1595 ms	3048 KiB

fountain

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

using ll = long long;
#define pb push_back

vector<int> d, c, r, v;
vector<int> nge_idx;

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

  int n, q, i, sum, j;
  bool met_end;

  cin >> n >> q;

  d = vector<int>(n + 1);
  c = vector<int>(n + 1);
  for (i = 1; i <= n; i++) {
    cin >> d[i] >> c[i];
  }

  // run next greater element
  nge_idx = vector<int>(n + 1, -1);
  stack<int> s;

  for (i = n; i >= 1; i--) {
    while (!s.empty() && d[s.top()] <= d[i]) {
      s.pop();
    }

    if (!s.empty()) {
      nge_idx[i] = s.top();
    }
    s.push(i);
  }

  r = vector<int>(q + 1);
  v = vector<int>(q + 1);
  for (i = 1; i <= q; i++) {
    cin >> r[i] >> v[i];

    j = r[i];
    sum = c[j];
    met_end = false;
    while (v[i] > sum) {
      if (nge_idx[j] == -1) {
        met_end = true;
        break;
      }

      j = nge_idx[j];
      sum += c[j];
    }

    if (met_end) {
      cout << "0\n";
      continue;
    }
    cout << j << "\n";
  }
  return 0;
}

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