oj.uz

Submission #1038890

# Submission time Handle Problem Language Result Execution time Memory
1038890 2024-07-30T08:41:48 Z Hanksburger Fountain (eJOI20_fountain) C++17
100 / 100
 235 ms 38476 KB 
#include <bits/stdc++.h>
using namespace std;
long long a[100005], b[100005][20], p[100005][20];
stack<long long> s;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, q;
    cin >> n >> q;
    for (long long i=1; i<=n; i++)
        cin >> a[i] >> b[i][0];
    a[n+1]=2e9, b[n+1][0]=2e9, p[n+1][0]=n+1;
    s.push(n+1);
    for (long long i=n; i>=1; i--)
    {
        while (a[s.top()]<=a[i])
            s.pop();
        p[i][0]=s.top();
        s.push(i);
    }
    for (long long i=1; i<20; i++)
        for (long long j=1; j<=n+1; j++)
            b[j][i]=b[j][i-1]+b[p[j][i-1]][i-1], p[j][i]=p[p[j][i-1]][i-1];
    for (long long i=1; i<=q; i++)
    {
        long long x, y;
        cin >> x >> y;
        for (long long j=19; j>=0; j--)
            if (b[x][j]<y)
                y-=b[x][j], x=p[x][j];
        cout << (x==n+1?0:x) << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 35364 KB Output is correct
2 Correct 169 ms 34384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 157 ms 35364 KB Output is correct
9 Correct 169 ms 34384 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 67 ms 20560 KB Output is correct
12 Correct 235 ms 38476 KB Output is correct
13 Correct 146 ms 37268 KB Output is correct
14 Correct 112 ms 36432 KB Output is correct
15 Correct 72 ms 36948 KB Output is correct