oj.uz

Submission #1009030

# Submission time Handle Problem Language Result Execution time Memory
1009030 2024-06-27T08:06:29 Z HishamAlshehri Fountain (eJOI20_fountain) C++17
100 / 100
 117 ms 45768 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 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 43080 KB Output is correct
2 Correct 91 ms 41236 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 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 91 ms 43080 KB Output is correct
9 Correct 91 ms 41236 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 44 ms 27872 KB Output is correct
12 Correct 117 ms 45768 KB Output is correct
13 Correct 89 ms 45012 KB Output is correct
14 Correct 60 ms 44884 KB Output is correct
15 Correct 54 ms 44760 KB Output is correct