Submission #1181603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181603		gabyferaq	Fountain (eJOI20_fountain)	C++20	0 / 100	1595 ms	3636 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
vector<long> dmt,cap, sgtf;
long query(long a,long b)
{
    long pos=a-1;
        while(b-cap[pos]>0)
        {
            b-=cap[pos], pos=sgtf[pos];
        }
        if(pos==-1) return 0;
        else return pos+1;
}
void solve()
{
    long n,q;
    cin>>n>>q;
    dmt.assign(n+1,0);
    cap.resize(n);
    sgtf.resize(n);
    long a,b;
    for(int i=0; i<n; i++)
    {
        cin>>a>>b;
        dmt[i]=a,cap[i]=b;
    }
    stack<long> pila;
    for(int i=n-1; i>=0; i--)
    {
        pila.push(i+1);
        if(dmt[pila.top()]==0)
        {
            sgtf[i]=-1, pila.pop();
        }
        else
        {
            if(dmt[i]<dmt[pila.top()]) sgtf[i]=pila.top();
            else
            {
                while(!pila.empty()&&(dmt[i]>dmt[pila.top()]||dmt[pila.top()]==0))
                {
                    pila.pop();
                }
                if(pila.empty())
                    sgtf[i]=-1;
                else sgtf[i]=pila.top();
            }
        }
    }
    while(q--)
    {
        cin>>a>>b;
        cout<<query(a,b)<<endl;
    }
}
int main()
{
    solve();
}

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