oj.uz

Submission #520209

# Submission time Handle Problem Language Result Execution time Memory
520209 2022-01-28T20:25:56 Z aris12345678 Fountain (eJOI20_fountain) C++14
100 / 100
 339 ms 29712 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define X first
#define Y second
const int mxN = 1e5+5;
const int mxL = 30;
int up[mxN][mxL], sum[mxN][mxL];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> d(n+1);
    vector<int> c(n+1);
    stack<pii> st;
    for(int i = 1; i <= n; i++) {
        scanf("%d %d", &d[i], &c[i]);
        while(!st.empty() && d[i] > st.top().X) {
            up[st.top().Y][0] = i;
            sum[st.top().Y][0] = c[st.top().Y];
            st.pop();
        }
        st.push({d[i], i});
    }
    while(!st.empty()) {
        up[st.top().Y][0] = 0;
        sum[st.top().Y][0] = c[st.top().Y];
        st.pop();
    }
    for(int j = 1; j < mxL; j++) {
        for(int i = 0; i <= n; i++) {
            up[i][j] = up[up[i][j-1]][j-1];
            sum[i][j] = sum[i][j-1]+sum[up[i][j-1]][j-1];
        }
    }
    while(q--) {
        int r, v;
        scanf("%d %d", &r, &v);
        for(int i = mxL-1; i >= 0; i--) {
            // cout << r << " " << i << " " << sum[r][i] << " " << v << "\n";
            if(sum[r][i] < v) {
                v -= sum[r][i];
                r = up[r][i];
            }
        }
        printf("%d\n", r);
    }
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 27048 KB Output is correct
2 Correct 292 ms 25460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 217 ms 27048 KB Output is correct
9 Correct 292 ms 25460 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 100 ms 16028 KB Output is correct
12 Correct 339 ms 29668 KB Output is correct
13 Correct 248 ms 29304 KB Output is correct
14 Correct 205 ms 28600 KB Output is correct
15 Correct 176 ms 29712 KB Output is correct