Submission #653241

#	Time	Username	Problem	Language	Result	Execution time	Memory
653241		Blagoj	Fountain (eJOI20_fountain)	C++14	100 / 100	303 ms	24512 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define endl '\n';

int seg[300003];
int d[100003], c[100003];
pair<int, int> f[100003][22];

void build(int k, int l, int r)
{
    if (l == r)
    {
        seg[k] = d[l];
        return;
    }
    build(k * 2, l, (l + r) / 2);
    build(k * 2 + 1, (l + r) / 2 + 1, r);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
}

int ans = INT_MAX;

void search(int k, int l, int r, int i, int j, int v)
{
    if (l > j || r < i || seg[k] <= v)
    {
        return;
    }
    if (l == r && d[l] > v)
    {
        ans = min(ans, l);
        return;
    }
    if (i <= l && r <= j)
    {
        if (seg[k * 2] > v)
        {
            search(k * 2, l, (l + r) / 2, i, j, v);
        }
        else
        {
            if (seg[k * 2 + 1] > v)
            {
                search(k * 2 + 1, (l + r) / 2 + 1, r, i, j, v);
            }
        }
        return;
    }
    search(k * 2, l, (l + r) / 2, i, j, v);
    search(k * 2 + 1, (l + r) / 2 + 1, r, i, j, v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i] >> c[i];
    }

    build(1, 1, n);
    f[n][0].second = c[n];
    f[n][0].first = 0;

    for (int i = 1; i < n; i++)
    {
        ans = INT_MAX;
        search(1, 1, n, i + 1, n, d[i]);
        if (ans == INT_MAX)
        {
            ans = 0;
        }
        f[i][0].first = ans;
        f[i][0].second = c[i];
    }
    
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            f[i][j].first = f[f[i][j - 1].first][j - 1].first;
            f[i][j].second = f[f[i][j - 1].first][j - 1].second + f[i][j - 1].second;
        }
    }

    while (q--)
    {
        int r, v;
        cin >> r >> v;
        for (int i = 19; i >= 0; i--)
        {
            if (v > f[r][i].second)
            {
                v -= f[r][i].second;
                r = f[r][i].first;
            }
        }
        cout << r << endl;
    }
}

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