Submission #1126684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126684		Szymon_Pilipczuk	Fountain (eJOI20_fountain)	C++20	100 / 100	609 ms	40716 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<vector<int>> pq;
    int n,p;
    cin>>n>>p;
    int c[n+1];
    int r[n+1];
    long long j[n+1][21][2];
    for(int i = 0;i<n;i++)
    {
        cin>>r[i];
        cin>>c[i];
        pq.push({-1*r[i],i});
        j[i][0][1] = c[i];
        while(pq.top()[0]*-1 < r[i])
        {
            j[pq.top()[1]][0][0] = i;
            pq.pop();
        }
    }
    while(!pq.empty())
    {
        j[pq.top()[1]][0][0] = n;
        pq.pop();
    }
    j[n][0][0] = n;
    j[n][0][1] = 1e9;
    for(int i = 1;i<21;i++)
    {
        for(int q = 0;q<n+1;q++)
        {
            j[q][i][0] = j[j[q][i-1][0]][i-1][0];
            j[q][i][1] = j[q][i-1][1] + j[j[q][i-1][0]][i-1][1];
        }
    }
    for(int i = 0;i<p;i++)
    {
        int s;
        long long a;
        cin>>s>>a;
        s--;
        for(int q = 20;q>=0;q--)
        {

            if(a - j[s][q][1] >0)
            {
                //cout<<q<<"\n";
                a -=j[s][q][1];
                s = j[s][q][0];
            }
        }
        if(s == n)
        {
            cout<<0<<"\n";
        }
        else
        {
            cout<<s+1<<"\n";
        }

    }
}

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