제출 #456360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456360		DobromirAngelov	Fountain (eJOI20_fountain)	C++14	100 / 100	296 ms	22144 KiB

fountain

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct rez
{
    int d,v;
};
struct torez
{
    int nom,v;
};
int n,q;
rez a[100005];
int logN;
torez spt[100005][20];
void getLog()
{
    int i=0;
    while((1<<i)<n)i++;
    if((1<<i)==n)logN=i;
    logN=i-1;
}
void make_SpTable()
{
    stack<int>st;
    for(int i=n;i>0;i--)
    {
        while(!st.empty()&&a[st.top()].d<=a[i].d)st.pop();
        if(st.empty())
        {
            st.push(i);
            spt[i][0].nom=0;
            spt[i][0].v=a[i].v;
            continue;
        }
        spt[i][0].nom=st.top();
        spt[i][0].v=a[i].v;
        st.push(i);
    }
    for(int j=1;j<=logN;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(spt[i][j-1].nom)spt[i][j].nom=spt[spt[i][j-1].nom][j-1].nom;
            if(spt[i][j-1].nom)spt[i][j].v=spt[i][j-1].v+spt[spt[i][j-1].nom][j-1].v;
            else spt[i][j].v=spt[i][j-1].v;
        }
    }
}
int query(int nom,int v)
{
    if(!nom)return 0;
    if(v<=a[nom].v)return nom;
    int i=0;
    while(spt[nom][i].v<v && spt[nom][i].nom>0 && i<logN)i++;
    if(spt[nom][i].v>=v&&i>0)i--;
    return query(spt[nom][i].nom,v-spt[nom][i].v);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
    cin>>a[i].d>>a[i].v;
}
getLog();
make_SpTable();
int nom,v;
for(int t=0;t<q;t++)
{
    cin>>nom>>v;
    cout<<query(nom,v)<<endl;
}
return 0;
}

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