Submission #702362

#	Time	Username	Problem	Language	Result	Execution time	Memory
702362		andrei_iorgulescu	Fountain (eJOI20_fountain)	C++14	100 / 100	269 ms	25024 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,q;
int d[100005],c[100005];
int dr[100005];
int sp[100005];
int nxt[100005][20];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> d[i] >> c[i];
    stack<int>st;
    for (int i = n; i >= 1; i--)
    {
        while (!st.empty() and d[st.top()] <= d[i])
            st.pop();
        if (!st.empty())
            dr[i] = st.top();
        else
            dr[i] = n + 1;
        st.push(i);
    }
    for (int i = n; i >= 1; i--)
        sp[i] = c[i] + sp[dr[i]];
    for (int i = 1; i <= n; i++)
        nxt[i][0] = dr[i];
    for (int j = 1; j <= 16; j++)
        for (int i = 1; i <= n; i++)
        {
            if (nxt[i][j - 1] == n + 1)
                nxt[i][j] = n + 1;
            else
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    for (int i = 1; i <= q; i++)
    {
        int r,v;
        cin >> r >> v;
        if (v > sp[r])
        {
            cout << "0\n";
            continue;
        }
        int pas = 16;
        while (pas != -1)
        {
            int wh = nxt[r][pas];
            //cout << r << ' ' << wh << '\n';
            if (wh != n + 1)
            {
                if (v > sp[r] - sp[wh])
                {
                    v -= (sp[r] - sp[wh]);
                    r = wh;
                }
            }
            pas--;
        }
        cout << r << '\n';
    }
    return 0;
}

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