oj.uz

Submission #963520

# Submission time Handle Problem Language Result Execution time Memory
963520 2024-04-15T08:59:07 Z ONEHUNDREDPUSHUPS Fountain (eJOI20_fountain) C++17
100 / 100
 274 ms 43880 KB 
#include<bits/stdc++.h>
#define sz size()
#define ll long long
#define t s.begin()
using namespace std;
const ll N = 100100;
const ll INF = 1e18;
ll up[N][20], sum[N][20];
void solve()
{
    ll n, q, i, j, k;
    cin >> n >> q;
    vector<ll> d(n + 5, INF), c(n + 5, INF);

    for(i = 1; i <= n; ++i)
    {
        cin >> d[i] >> c[i];
    }

    set<pair<ll, int>> s;

    for(i = 1; i <= n; ++i)
    {
        while(s.sz && (*t).first < d[i])
        {
            up[(*t).second][0] = i;
            s.erase(t);
        }
        s.insert({d[i], i});
    }

    for(i = n; i >= 1; --i)
    {
        sum[i][0] = c[up[i][0]];
        for(j = 1; j < 20; ++j)
            up[i][j] = up[up[i][j - 1]][j - 1],
            sum[i][j] = sum[i][j - 1] + sum[up[i][j - 1]][j - 1];
    }

//    for(i = 1; i <= n; ++i)
//        cout << up[i][0] << ' ';
//    return;

    while(q--)
    {
        ll r, v;
        cin >> r >> v;
        v -= c[r];
        for(j = 19; j >= 0; --j)
        {
            if(sum[r][j] && sum[r][j] <= v)
            {
                v -= sum[r][j];
                r = up[r][j];
            }
        }
        if(v > 0) r = up[r][0];
        cout << r << '\n';
    }


}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:11:20: warning: unused variable 'k' [-Wunused-variable]
   11 |     ll n, q, i, j, k;
      |                    ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2408 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 36528 KB Output is correct
2 Correct 191 ms 36692 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2408 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 179 ms 36528 KB Output is correct
9 Correct 191 ms 36692 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 56 ms 24404 KB Output is correct
12 Correct 274 ms 38564 KB Output is correct
13 Correct 167 ms 38640 KB Output is correct
14 Correct 111 ms 37456 KB Output is correct
15 Correct 100 ms 43880 KB Output is correct