Submission #383327

#	Time	Username	Problem	Language	Result	Execution time	Memory
383327		aris12345678	Fountain (eJOI20_fountain)	C++14	100 / 100	413 ms	29920 KiB

fountain

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

const int mxN = 1e5+5, mxL = 30;
int diam[mxN], cap[mxN], dp[mxN][mxL], wat[mxN][mxL];

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &diam[i], &cap[i]);
    priority_queue<pair<int, int> > pq;
    for(int i = 1; i <= n; i++) {
        while(!pq.empty() && -pq.top().first < diam[i]) {
            dp[pq.top().second][0] = i;
            pq.pop();
        }
        pq.push({-diam[i], i});
    }
    while(!pq.empty()) {
        dp[pq.top().second][0] = 0;
        pq.pop();
    }
    for(int i = 1; i <= n; i++)
        wat[i][0] = cap[i];
    dp[0][0] = wat[0][0] = 0;
    for(int i = 1; i < mxL; i++) {
        for(int u = 0; u <= n; u++)
            dp[u][i] = dp[dp[u][i-1]][i-1], wat[u][i] = wat[u][i-1]+wat[dp[u][i-1]][i-1];
    }
    while(q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        for(int i = mxL-1; i >= 0; i--) {
            if(wat[l][i] >= r) continue;
            r -= wat[l][i], l = dp[l][i];
        }
        printf("%d\n", l);
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:9:10: 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:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |         scanf("%d%d", &diam[i], &cap[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%d%d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~

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