Submission #391068

#	Time	Username	Problem	Language	Result	Execution time	Memory
391068		aris12345678	Fountain (eJOI20_fountain)	C++14	100 / 100	370 ms	35180 KiB

fountain

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

const int mxN = 1e5+5, mxL = 20;
vector<int> adj[mxN];
int d[mxN], c[mxN], up[mxN][mxL];
long long sum[mxN][mxL];

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &d[i], &c[i]);
    stack<pair<int, int> > st;
    for(int i = 1; i <= n; i++) {
        while(!st.empty() && st.top().first < d[i]) {
            adj[i].push_back(st.top().second);
            up[st.top().second][0] = i;
            st.pop();
        }
        st.push({d[i], i});
    }
    while(!st.empty()) {
        adj[0].push_back(st.top().second);
        up[st.top().second][0] = 0;
        st.pop();
    }
    for(int i = 1; i <= n; i++)
        sum[i][0] = c[i];
    up[0][0] = sum[0][0] = 0;
    for(int i = 1; i < mxL; i++) {
        for(int u = 0; u <= n; u++)
            up[u][i] = up[up[u][i-1]][i-1], sum[u][i] = sum[u][i-1]+sum[up[u][i-1]][i-1];
    }
    while(q--) {
        int r, v;
        scanf("%d%d", &r, &v);
        for(int i = mxL-1; i >= 0; i--) {
            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:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         scanf("%d%d", &d[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         scanf("%d%d", &r, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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