Submission #1183684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183684		meicris	Fountain (eJOI20_fountain)	C++17	0 / 100	20 ms	24136 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
vector<long> dmt,cap;
vector<vector<int>> sgtf,sgtv;
int aux;
long query(long a,long b, long n)
{
    for(int i=18; i>=0; i--){
        if(a==n+1) break;
        if(sgtv[a][i]<b){
            b-=sgtv[a][i];
            a=sgtf[a][i];
        }
    }
    cout<<(a>n?0:a)<<"\n";
    return 0;
}
void solve()
{
    long n,q;
    cin>>n>>q;
    dmt.assign(n+1,1e5+10);
    cap.assign(n+1,1e5+10);
    sgtf.resize(n+1,vector<int> (20,0));
    sgtv.resize(n+1,vector<int> (20,0));
    long a,b;
    for(int i=1; i<=n; i++)
    {
        cin>>a>>b;
        dmt[i]=a,cap[i]=b;
    }
    stack<long> pila;
    pila.push(0);
    for(int i=n; i>=1; i--)
    {
        sgtv[i][0]=cap[i];
        while(dmt[i]>=dmt[pila.top()])
        {
            pila.pop();
        }
        sgtf[i][0]=pila.top();
        pila.push(i);
    }
    for(int j=1; j<20; j++){
        int cont=0;
        for(int i=1; i<n+1; i++)
        {
            int parent=sgtf[i][j-1];
            sgtv[i][j]=sgtv[i][j-1]+sgtv[parent][j-1];
            sgtf[i][j]=sgtf[parent][j-1];
        }
    }
    while(q--)
    {
        cin>>a>>b;
        query(a,b,n);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

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