oj.uz

Submission #690852

# Submission time Handle Problem Language Result Execution time Memory
690852 2023-01-30T13:09:10 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 265 ms 17848 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5 + 5, LOG = 20, INF = 2e9;
int up[MAX][LOG], sum[MAX][LOG], D[MAX];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin>>n>>q;
    for (int i = 1; i <= n; i++) cin>>D[i]>>sum[i][0];
    
    D[n + 1] = INF;
    sum[n + 1][0] = INF;
    up[n + 1][0] = n + 1;

    stack<int> s;
    s.push(n + 1);
    for (int i = n; i >= 1; i--)
    {
        while(D[s.top()] <= D[i]) s.pop();
        up[i][0] = s.top();
        s.push(i);
    }
    for (int i = 1; i < LOG; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            up[j][i] = up[up[j][i - 1]][i - 1];
            sum[j][i] = sum[up[j][i - 1]][i - 1] + sum[j][i - 1];
        }
    }
    
    for (int i = 0; i < q; i++)
    {
        int r, v;
        cin>>r>>v;
        for (int j = LOG - 1; j >= 0; j--)
        {
            if(v > sum[r][j]){
                v -= sum[r][j];
                r = up[r][j];
            }
        }
        if(r == n + 1) cout<<0<<'\n';
        else cout<<r<<'\n';
    }
    
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 16680 KB Output is correct
2 Correct 198 ms 15520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 165 ms 16680 KB Output is correct
9 Correct 198 ms 15520 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 77 ms 9824 KB Output is correct
12 Correct 265 ms 17848 KB Output is correct
13 Correct 169 ms 17576 KB Output is correct
14 Correct 155 ms 17528 KB Output is correct
15 Correct 110 ms 17484 KB Output is correct