Submission #1120027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120027		boris_7	Fountain (eJOI20_fountain)	C++17	100 / 100	705 ms	45476 KiB

fountain

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