oj.uz

Submission #1009031

# Submission time Handle Problem Language Result Execution time Memory
1009031 2024-06-27T08:06:44 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 128 ms 45776 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
// #define pi acos(-1)
#define double long double
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")

constexpr int maxn = 1000001;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, q;
int jump[maxn][21][2], d[maxn], c[maxn], nxt[maxn];

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> d[i] >> c[i];
    vector<int>ve;
    for (int i = n - 1; i >= 0; i--)
    {
        while(ve.size() && d[ve.back()] <= d[i])
        {
            ve.pop_back();
        }
        if (ve.size())
            nxt[i] = ve.back();
        ve.push_back(i);
    }

    for (int i = 0; i < n; i++)
    {
        jump[i][0][0] = c[i];
        jump[i][0][1] = nxt[i];
    }

    for (int j = 1; j < 21; j++)
    {
        for (int i = 0; i < n; i++)
        {
            jump[i][j][0] = jump[i][j - 1][0] + jump[jump[i][j - 1][1]][j - 1][0];
            jump[i][j][1] = jump[jump[i][j - 1][1]][j - 1][1];
        }
    }
    
    while (q--)
    {
        int r, v;
        cin >> r >> v;
        r--;
        
        for (int i = 20; i >= 0; i--)
        {
            while (jump[r][i][0] < v)
            {
                if (r == n - 1)
                {
                    r = -1;
                    break;
                }
                v -= jump[r][i][0];
                r = jump[r][i][1];
            }
            if (r < 0)
                break;
        }

        cout << r + 1 << "\n";
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 43116 KB Output is correct
2 Correct 91 ms 41168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 77 ms 43116 KB Output is correct
9 Correct 91 ms 41168 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 40 ms 28060 KB Output is correct
12 Correct 128 ms 45776 KB Output is correct
13 Correct 99 ms 45012 KB Output is correct
14 Correct 64 ms 44884 KB Output is correct
15 Correct 60 ms 44880 KB Output is correct