oj.uz

Submission #489761

# Submission time Handle Problem Language Result Execution time Memory
489761 2021-11-24T13:09:08 Z Biccam Fountain (eJOI20_fountain) C++14
100 / 100
 485 ms 21272 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 4 ms 464 KB Output is correct
7 Correct 3 ms 464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 18832 KB Output is correct
2 Correct 357 ms 17952 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 4 ms 464 KB Output is correct
7 Correct 3 ms 464 KB Output is correct
8 Correct 326 ms 18832 KB Output is correct
9 Correct 357 ms 17952 KB Output is correct
10 Correct 4 ms 464 KB Output is correct
11 Correct 192 ms 11296 KB Output is correct
12 Correct 485 ms 21268 KB Output is correct
13 Correct 437 ms 20864 KB Output is correct
14 Correct 354 ms 20044 KB Output is correct
15 Correct 369 ms 21272 KB Output is correct