oj.uz

Submission #383327

# Submission time Handle Problem Language Result Execution time Memory
383327 2021-03-29T16:07:59 Z aris12345678 Fountain (eJOI20_fountain) C++14
100 / 100
 413 ms 29920 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 27264 KB Output is correct
2 Correct 309 ms 25568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 285 ms 27264 KB Output is correct
9 Correct 309 ms 25568 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 145 ms 16276 KB Output is correct
12 Correct 413 ms 29896 KB Output is correct
13 Correct 313 ms 29656 KB Output is correct
14 Correct 244 ms 28652 KB Output is correct
15 Correct 213 ms 29920 KB Output is correct