Submission #1305895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305895		ivano_bozhinovski	Fountain (eJOI20_fountain)	C++20	100 / 100	362 ms	28616 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pii pair<int,int>
#define pb push_back
typedef long long ll;

const int maxn=1e5+5;
const int maxlog=20;
vector<int> adj[maxn],c(maxn);
int up[maxn][maxlog],sumup[maxn][maxlog],dep[maxn];

void dfs(int v,int par,int depth)
{
    up[v][0]=par;
    if(par!=-1)sumup[v][0]=c[par];
    dep[v]=depth;
    for(int i=1;i<maxlog;i++)
    {
        if(up[v][i-1]!=-1)
        {
            up[v][i]=up[up[v][i-1]][i-1];
            sumup[v][i]=sumup[v][i-1]+sumup[up[v][i-1]][i-1];
        }
        else up[v][i]=-1;
    }
    for(auto x:adj[v])
    {
        if(x!=par)dfs(x,v,depth+1);
    }

}

int qry(int node,int s)
{
    if(c[node]>=s)return node;
    int ans=c[node];
    for(int i=maxlog-1;i>=0;i--)
    {
        if(up[node][i]!=-1&&ans+sumup[node][i]<s)
        {
            ans+=sumup[node][i];
            node=up[node][i];
        }
    }
    return up[node][0];
}


int main()
{
    //freopen("input.txt","r",stdin);
    int n,q;
    cin>>n>>q;
    int d[n+1];
    for(int i=1;i<=n;i++)cin>>d[i]>>c[i];
    stack<int> st;
    c[0]=2e9;
    for(int i=1;i<=n;i++)
    {
        while(!st.empty()&&d[st.top()]<d[i])
        {
            //adj[st.top()].push_back(i);
            adj[i].push_back(st.top());
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        //adj[st.top()].push_back(0);
        adj[0].push_back(st.top());
        st.pop();
    }

    dfs(0,-1,0);
    int r,v;
    for(int i=1;i<=q;i++)
    {
        cin>>r>>v;
        cout<<qry(r,v)<<endl;
    }
}

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