Submission #404494

#TimeUsernameProblemLanguageResultExecution timeMemory
404494radaiosm7Fountain (eJOI20_fountain)C++98
100 / 100
245 ms17604 KiB
#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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...