oj.uz

Submission #738642

# Submission time Handle Problem Language Result Execution time Memory
738642 2023-05-09T10:04:07 Z aykhn Fountain (eJOI20_fountain) C++14
100 / 100
 698 ms 36832 KB 
#include <bits/stdc++.h>


/*
    author: aykhn
    5/4/2023
*/

using namespace std;

typedef long long ll;

const int oo = INT_MAX;
const ll ooo = LONG_MAX;
const ll mod = 1e9 + 7;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0);
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

vector<vector<pll>> table(18, vector<pll> (100001));
int main()
{
    ll n, q;
    cin >> n >> q;

    vector<pll> v(n + 1);

    for (ll i = 1; i <= n; i++) cin >> v[i].fi >> v[i].se;

    stack<ll> s;

    vector<ll> next(n + 1);

    next[n] = 0;

    for (ll i = n; i > 0; i--)
    {
        while (!s.empty() && v[s.top()].fi <= v[i].fi) s.pop();

        if (s.empty()) next[i] = 0;
        else next[i] = s.top();

        s.push(i);
    }

    v[0].fi = v[0].se = 0;

    for (ll i = 1; i <= n; i++)
    {
        table[0][i].fi = next[i];
        table[0][i].se = v[i].se;
    }

    for (ll i = 1; i <= 17; i++)
    {
        for (ll j = 0; j <= n; j++)
        {
            table[i][j].fi = table[i - 1][table[i - 1][j].fi].fi;
            table[i][j].se = table[i - 1][table[i - 1][j].fi].se + table[i - 1][j].se;
        }
    }

    while (q--)
    {
        ll r, x;
        cin >> r >> x;

        for (ll i = 17; i >= 0; i--)
        {
            if (table[i][r].se < x)
            {
                x -= table[i][r].se;
                r = table[i][r].fi;
            }
        }

        cout << r << endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30036 KB Output is correct
2 Correct 13 ms 30036 KB Output is correct
3 Correct 15 ms 30044 KB Output is correct
4 Correct 23 ms 30040 KB Output is correct
5 Correct 17 ms 30032 KB Output is correct
6 Correct 17 ms 30036 KB Output is correct
7 Correct 17 ms 29996 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 35096 KB Output is correct
2 Correct 509 ms 35248 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30036 KB Output is correct
2 Correct 13 ms 30036 KB Output is correct
3 Correct 15 ms 30044 KB Output is correct
4 Correct 23 ms 30040 KB Output is correct
5 Correct 17 ms 30032 KB Output is correct
6 Correct 17 ms 30036 KB Output is correct
7 Correct 17 ms 29996 KB Output is correct
8 Correct 453 ms 35096 KB Output is correct
9 Correct 509 ms 35248 KB Output is correct
10 Correct 17 ms 30036 KB Output is correct
11 Correct 261 ms 32112 KB Output is correct
12 Correct 698 ms 36832 KB Output is correct
13 Correct 576 ms 35824 KB Output is correct
14 Correct 477 ms 34928 KB Output is correct
15 Correct 473 ms 35148 KB Output is correct