oj.uz

Submission #1120027

# Submission time Handle Problem Language Result Execution time Memory
1120027 2024-11-27T18:29:59 Z boris_7 Fountain (eJOI20_fountain) C++17
100 / 100
 705 ms 45476 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<ll>>gp;


void solve() {
    ll n,q;
    cin>>n>>q;
    gp = vector<vector<ll>>(n);
    vector<ll>d(n+1),c(n+1);
    d.back()=1e15;
    c.back()=1e15;
    for(ll i = 0;i<n;i++){
        cin>>d[i]>>c[i];
    }
    stack<ll>st;
    st.push(n);
    vector<vector<pair<ll,ll>>>up(n+1,vector<pair<ll,ll>>(20,{n,0}));
    for(ll i = n-1;i>=0;i--){
        while(st.size() && d[st.top()]<=d[i]){
            st.pop();
        }
        up[i][0]={st.top(),c[i]};
        st.push(i);
    }
    for(ll i = 1;i<20;i++){
        for(ll j = 0;j<n;j++){
            ll ne = up[j][i-1].first;
            up[j][i]={up[ne][i-1].first,up[j][i-1].second+up[ne][i-1].second};
        }
    }
    while(q--){
        ll ind,val;
        cin>>ind>>val;
        --ind;
        // cout<<i<<" "<<ind<<" "<<val<<endl;
        // cout<<up[ind][1].second<<endl;
        for(ll i = 19;i>=0;--i){
            if(up[ind][i].second<val){
                val-=up[ind][i].second;
                ind =up[ind][i].first;
            }
        }
        if(ind == n) cout<<0<<endl;
        else cout<<ind+1<<endl;
    }
    
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}
/*
5
0
5
4
2
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 42092 KB Output is correct
2 Correct 502 ms 39244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 399 ms 42092 KB Output is correct
9 Correct 502 ms 39244 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 231 ms 24296 KB Output is correct
12 Correct 705 ms 45476 KB Output is correct
13 Correct 548 ms 44364 KB Output is correct
14 Correct 440 ms 43596 KB Output is correct
15 Correct 400 ms 43860 KB Output is correct