Submission #520209

#	Time	Username	Problem	Language	Result	Execution time	Memory
520209		aris12345678	Fountain (eJOI20_fountain)	C++14	100 / 100	339 ms	29712 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40