oj.uz

Submission #1021585

# Submission time Handle Problem Language Result Execution time Memory
1021585 2024-07-12T20:29:29 Z mar Fountain (eJOI20_fountain) C++14
100 / 100
 558 ms 53700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100006;
const int loga = 30;

ll d[maxn],c[maxn][loga];
ll nxt[maxn][loga];


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()) {
            nxt[i+1][0] = st.top()+1;
        }
        st.push(i);
    }
    
    for(ll i=1; i<loga; i++) {
        for(ll j=1; j<=n; j++) {
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
            c[j][i] = c[j][i-1]+c[nxt[j][i-1]][i-1];    
        }
    }
    
    while(q--) {
        int ans, w; cin>>ans>>w;
        for(int i=loga-1; i>=0; i--) {
            if(w>c[ans][i]) {
                w-=c[ans][i];
                ans=nxt[ans][i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 964 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 49744 KB Output is correct
2 Correct 394 ms 46676 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 964 KB Output is correct
8 Correct 382 ms 49744 KB Output is correct
9 Correct 394 ms 46676 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 228 ms 29136 KB Output is correct
12 Correct 558 ms 53700 KB Output is correct
13 Correct 470 ms 52956 KB Output is correct
14 Correct 408 ms 52304 KB Output is correct
15 Correct 397 ms 52564 KB Output is correct