Submission #1038890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038890		Hanksburger	Fountain (eJOI20_fountain)	C++17	100 / 100	235 ms	38476 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
long long a[100005], b[100005][20], p[100005][20];
stack<long long> s;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, q;
    cin >> n >> q;
    for (long long i=1; i<=n; i++)
        cin >> a[i] >> b[i][0];
    a[n+1]=2e9, b[n+1][0]=2e9, p[n+1][0]=n+1;
    s.push(n+1);
    for (long long i=n; i>=1; i--)
    {
        while (a[s.top()]<=a[i])
            s.pop();
        p[i][0]=s.top();
        s.push(i);
    }
    for (long long i=1; i<20; i++)
        for (long long j=1; j<=n+1; j++)
            b[j][i]=b[j][i-1]+b[p[j][i-1]][i-1], p[j][i]=p[p[j][i-1]][i-1];
    for (long long i=1; i<=q; i++)
    {
        long long x, y;
        cin >> x >> y;
        for (long long j=19; j>=0; j--)
            if (b[x][j]<y)
                y-=b[x][j], x=p[x][j];
        cout << (x==n+1?0:x) << '\n';
    }
}

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