Submission #440544

#	Time	Username	Problem	Language	Result	Execution time	Memory
440544		Tenis0206	Fountain (eJOI20_fountain)	C++11	100 / 100	345 ms	26296 KiB

fountain

#include <bits/stdc++.h>

using namespace std;
struct rezervor
{
    int d,c;
};
struct binary_lifting
{
    int poz,val;
};
int n,q;
binary_lifting u[100005][25];
rezervor v[100005];
int query(int val, int poz)
{
    if(v[poz].c>=val)
    {
        return poz;
    }
    val-=v[poz].c;
    for(int p=20;p>=0;p--)
    {
        if(u[poz][p].val<val)
        {
            if(u[poz][p].poz==0)
            {
                return 0;
            }
            val-=u[poz][p].val;
            poz = u[poz][p].poz;
        }
    }
    return u[poz][0].poz;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].d>>v[i].c;
    }
    stack<int> st;
    for(int i=n;i>=1;i--)
    {
        while(!st.empty() && v[st.top()].d<=v[i].d)
        {
            st.pop();
        }
        if(st.empty())
        {
            u[i][0].poz = 0;
            u[i][0].val = 0;
        }
        else
        {
            u[i][0].poz = st.top();
            u[i][0].val = v[st.top()].c;
        }
        st.push(i);
    }
    for(int k=1;k<=20;k++)
    {
        for(int i=1;i<=n;i++)
        {
            u[i][k].poz = u[u[i][k-1].poz][k-1].poz;
            u[i][k].val = u[i][k-1].val + u[u[i][k-1].poz][k-1].val;
        }
    }
    for(int i=1;i<=q;i++)
    {
        int val,poz;
        cin>>poz>>val;
        cout<<query(val,poz)<<'\n';
    }
    return 0;
}

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