제출 #1245283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245283		boyan2010	Fountain (eJOI20_fountain)	C++20	100 / 100	495 ms	40004 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
long long n,q,r,vol;
long long d[100001],c[100001],p[100001],bl[100001][20],cap[100001][20];
bool u[100001][20],v[100001][20];
stack<long long>st;
long long f(long long i,long long k)
{
    if(k==0)
    {
        bl[i][k]=p[i];
        return p[i];
    }
    if(u[i][k])
    {
        return bl[i][k];
    }
    u[i][k]=1;
    bl[i][k]=f(f(i,k-1),k-1);
    return bl[i][k];
}
long long ff(long long i,long long k)
{
    if(k==0)
    {
        cap[i][k]=c[p[i]];
        return c[p[i]];
    }
    if(v[i][k])
    {
        return cap[i][k];
    }
    v[i][k]=1;
    cap[i][k]=ff(i,k-1)+ff(f(i,k-1),k-1);
    return cap[i][k];
}
long long fft()
{
    long long ans=0;
    vol-=c[r];
    for(long long i=19;i>=0;i--)
    {
        //cout<<r<<" "<<i<<" "<<ff(r,i)<<"\n";
        if(ans+ff(r,i)<vol)
        {
            ans+=ff(r,i);
            r=f(r,i);
        }
    }
    if(vol<=0)
    {
        return r;
    }
    return p[r];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(long long i=1;i<=n;i++)
    {
        cin>>d[i]>>c[i];
    }
    d[0]=INT_MAX;
    c[0]=0;
    st.push(n);
    for(long long i=1;i<=n;i++)
    {
        while(!st.empty() && d[st.top()]<d[i])
        {
            p[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        p[st.top()]=0;
        st.pop();
    }
    for(long long i=0;i<q;i++)
    {
        cin>>r>>vol;
        cout<<fft()<<"\n";
    }
    return 0;
}

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