제출 #1150629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150629		csibe_csavo	Fountain (eJOI20_fountain)	C++20	100 / 100	124 ms	17608 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
const int c=1e5+10,k=19;
int kov[c][k],ert[c][k],szel[c],kap[c];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q; cin>>n>>q;
    for(int i=1; i<=n; i++)
        cin>>szel[i]>>kap[i];
    stack<int> s;
    s.push(n+1);
    szel[n+1]=1e9+10;
    for(int i=n; i>0; i--)
    {
        while(szel[s.top()]<=szel[i]) s.pop();
        kov[i][0]=s.top();
        ert[i][0]=kap[i];
        s.push(i);
    }
    for(int j=1; j<k; j++)
        for(int i=1; i<=n; i++)
        {
            kov[i][j]=kov[kov[i][j-1]][j-1];
            ert[i][j]=ert[i][j-1]+ert[kov[i][j-1]][j-1];
        }
    while(q--)
    {
        int kezd,hany; cin>>kezd>>hany;
        for(int i=k-1; i>=0; i--)
        {
            if(kezd==n+1) break;
            if(ert[kezd][i]<hany)
            {
                //cout<<kezd<<" "<<hany<<endl;
                hany-=ert[kezd][i];
                kezd=kov[kezd][i];
                //cout<<kezd<<" "<<hany<<endl;
            }
        }
        cout<<(kezd>n?0:kezd)<<"\n";
    }
}

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