Submission #1262653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262653		iordache_	Fountain (eJOI20_fountain)	C++20	100 / 100	161 ms	36008 KiB

fountain

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5,LOG=20;
int d[N],v[N];
int to[N];
int up[N][LOG],sum[N][LOG];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>d[i]>>v[i];
    stack<int> st;
    for(int i=n;i>=1;--i)
    {
        while(!st.empty()&&d[i]>=d[st.top()]) st.pop();
        if(!st.empty()) to[i]=st.top();
        else to[i]=0;
        st.push(i);
    }
    for(int i=1;i<=n;++i) up[i][0]=to[i],sum[i][0]=v[to[i]];
    for(int j=1;j<LOG;++j)
    {
        for(int i=1;i<=n;++i) up[i][j]=up[up[i][j-1]][j-1],sum[i][j]=sum[i][j-1]+sum[up[i][j-1]][j-1];
    }
    while(q--)
    {
        int poz,val;cin>>poz>>val;
        if(val<=v[poz]) {cout<<poz<<'\n';continue;}
        for(int b=LOG-1;b>=0;--b)
        {
            if(val>sum[poz][b]-v[up[poz][b]]+v[poz])
            {
                val-=sum[poz][b]-v[up[poz][b]]+v[poz];
                poz=up[poz][b];
            }
        }
        cout<<poz<<'\n';
    }
}

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