Submission #1182383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182383		gabyferaq	Fountain (eJOI20_fountain)	C++20	0 / 100	914 ms	589824 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
vector<long> dmt,cap;
vector<vector<int>> sgtf,sgtv;
int aux;
long query(long a,long b)
{
    aux=0;
    if(b<=sgtv[a][0]) return a;
    else {while(b>sgtv[a][aux]&&sgtv[a][aux]!=*sgtv[a].end())
        {
            sgtv[a][aux++];
        }
        if(sgtv[a][aux]==*sgtv[a].end()) return sgtf[a][*prev(sgtf[a].end())];
        else return sgtf[a][aux-1];}
}
void solve()
{
    long n,q;
    cin>>n>>q;
    dmt.assign(n+2,0);
    cap.assign(n+1,0);
    sgtf.resize(n+2,vector<int> (1,0));
    sgtv.resize(n+2,vector<int> (1,0));
    long a,b;
    for(int i=1; i<=n; i++)
    {
        cin>>a>>b;
        dmt[i]=a,cap[i]=b;
    }
    stack<long> pila;
    for(int i=n; i>=1; i--)
    {
        pila.push(i+1);
        sgtv[i][0]=cap[i];
        if(dmt[pila.top()]==0)
        {
            sgtf[i][0]=0, pila.pop();
        }
        else
        {
            if(dmt[i]<dmt[pila.top()]) sgtf[i][0]=pila.top();
            else
            {
                while(!pila.empty()&&(dmt[i]>dmt[pila.top()]||dmt[pila.top()]==0))
                {
                    pila.pop();
                }
                if(pila.empty())
                    sgtf[i][0]=0;
                else sgtf[i][0]=pila.top();
            }
        }
    }
    int s;
    for(int i=1;i<=n;i++)
    {
        s=i;
        while(s){
        s=sgtf[s][0];
        sgtf[i].push_back(sgtf[s][0]);}
        s=sgtv[i][0];
        for(auto x:sgtf[i])
        {
            sgtv[i].push_back(s+sgtv[x][0]);
            s+=sgtv[x][0];
        }
    }
    while(q--)
    {
        cin>>a>>b;
        cout<<query(a,b)<<endl;
    }
}
int main()
{
    solve();
}

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