Submission #1132068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132068		c32ardash	Fountain (eJOI20_fountain)	C++17	100 / 100	160 ms	39928 KiB

fountain

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX=1e5+5, INF=1e9+5;
int lift[NMAX][17], sp[NMAX][17], p[NMAX], d[NMAX], c[NMAX], n, q;
vector<int> adj[NMAX];
stack<int> st;

void DFS(int u)
{
    lift[u][0]=p[u]; sp[u][0]=min(c[u]+c[p[u]], INF);
    for(int i=1;i<=16;i++)
    {
        lift[u][i]=lift[lift[u][i-1]][i-1];
        sp[u][i]=min(sp[u][i-1]+sp[lift[u][i-1]][i-1]-c[lift[u][i-1]], INF);
    }
    for(auto v:adj[u])
        DFS(v);
}

int caut_bin(int u, int s)
{
    if(s<=c[u])
        return u;
    int r=u, pas=16, st=0;
    while(pas>=0)
    {
        if(st+sp[r][pas]<s)
        {
            st+=(sp[r][pas]-c[lift[r][pas]]);
            r=lift[r][pas];
        }
        pas--;
    }
    return p[r];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    d[0]=c[0]=INF;
    for(int i=1;i<=n;i++)
        cin>>d[i]>>c[i];
    st.push(0);
    for(int i=n;i>=1;i--)
    {
        while(d[i]>=d[st.top()])
            st.pop();
        p[i]=st.top();
        adj[p[i]].push_back(i);
        st.push(i);
    }
    DFS(0);
    while(q--)
    {
        int r, v;
        cin>>r>>v;
        cout<<caut_bin(r, v)<<'\n';
    }
    return 0;
}

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