Submission #489761

#	Time	Username	Problem	Language	Result	Execution time	Memory
489761		Biccam	Fountain (eJOI20_fountain)	C++14	100 / 100	485 ms	21272 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define repV(i, a, n) for (int i = n; i >= a; i--)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
constexpr int M = 1e5 + 5;
constexpr int LOG = 20;
int n, q, d, c, r, v, ans;
int dp[M][LOG], w[M][LOG];
priority_queue<pii> pq;

void solve()
{
    cin >> n >> q;
    rep(i, 1, n)
    {
        cin >> d >> w[i][0];
        while (pq.size() && pq.top().st > -d)
        {
            dp[pq.top().nd][0] = i; // ustawiam poprzedni
            pq.pop();
        }
        pq.push({-d, i});
    }
    /*rep(i, 1, n)
    {
        rep(j, 1, LOG - 1)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
    cout << endl;
    while (pq.size())
    {
        // dp[pq.top().st][0] = 0;
        pq.pop();
    }
    rep(j, 1, LOG - 1)
    {
        rep(i, 1, n)
        {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
            w[i][j] = w[dp[i][j - 1]][j - 1] + w[i][j - 1];
        }
    }
    /*rep(i, 1, n)
    {
        rep(j, 1, LOG - 1)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
}

void odp()
{
    rep(i, 1, q)
    {
        cin >> r >> v;
        repV(j, 0, LOG - 1)
        {
            if (v <= w[r][j])
                continue;
            v -= w[r][j];
            r = dp[r][j];
        }
        cout << r << endl;
    }
}

int main()
{
    IOS
    solve();
    odp();
}

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