oj.uz

Submission #1048649

# Submission time Handle Problem Language Result Execution time Memory
1048649 2024-08-08T08:56:41 Z mar Fountain (eJOI20_fountain) C++14
100 / 100
 442 ms 33404 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100007;
const int logi=17;
 
ll d[maxn],c[maxn][logi];
ll up[maxn][logi];

int main() {
    int n,q; cin>>n>>q;
    for(int i=0; i <n; i++) {
        cin>>d[i]>>c[i+1][0];
    }
    stack<int>st;
    for(int i=n-1; i>=0; i--) {
        while(!st.empty() && d[st.top()] <= d[i]) st.pop();
        if(!st.empty()) up[i+1][0] = st.top()+1;
        st.push(i);
    }
    for(int i=1; i<logi; i++) {
        for(int j=1; j<=n; j++) {
            up[j][i] = up[up[j][i-1]][i-1];
            c[j][i] = c[j][i-1]+c[up[j][i-1]][i-1];    
        }
    }
    while(q--) {
        int ans, w; cin>>ans>>w;
        for(int i=logi-1; i>=0; i--) {
            if(w>c[ans][i]) {
                w-=c[ans][i];
                ans=up[ans][i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4564 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 31616 KB Output is correct
2 Correct 285 ms 31828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4564 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 254 ms 31616 KB Output is correct
9 Correct 285 ms 31828 KB Output is correct
10 Correct 6 ms 4700 KB Output is correct
11 Correct 186 ms 21328 KB Output is correct
12 Correct 442 ms 33404 KB Output is correct
13 Correct 372 ms 32632 KB Output is correct
14 Correct 299 ms 31916 KB Output is correct
15 Correct 289 ms 32084 KB Output is correct