Submission #404494

#	Time	Username	Problem	Language	Result	Execution time	Memory
404494		radaiosm7	Fountain (eJOI20_fountain)	C++98	100 / 100	245 ms	17604 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
int n, q, r, i, j;
long long d[100005], c[100005], v, pref[100005];
stack<pair<long long, int> > diams;
int up[100005][20];
int p[100005];
int main() {
  scanf("%d%d", &n, &q);

  for (i=1; i <= n; ++i) {
    scanf("%lld%lld", &d[i], &c[i]);
  }

  diams.push(make_pair(LONG_LONG_MAX, 0));
  pref[0] = 0LL;

  for (i=0; i < 20; ++i) {
    up[0][i] = 0;
  }

  for (i=n; i >= 1; --i) {
    while (diams.top().first <= d[i]) diams.pop();
    p[i] = diams.top().second;
    diams.push(make_pair(d[i], i));
    pref[i] = pref[p[i]]+c[i];
    up[i][0] = p[i];

    for (j=1; j < 20; ++j) {
      up[i][j] = up[up[i][j-1]][j-1];
    }
  }

  while (q--) {
    scanf("%d%lld", &r, &v);
    if (v > pref[r]) {
      printf("0\n");
    }

    else {
      for (i=19; i >= 0; --i) {
        if (v > pref[r]-pref[up[r][i]]) {
          v -= pref[r]-pref[up[r][i]];
          r = up[r][i];
        }
      }
      printf("%d\n", r);
    }
  }

  return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%lld%lld", &d[i], &c[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%lld", &r, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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