oj.uz

Submission #1024512

# Submission time Handle Problem Language Result Execution time Memory
1024512 2024-07-16T06:36:34 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 522 ms 36224 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, q;
    cin>>n>>q;
    int L=log2(n)+1;
    int d[n+1], c[n+1];
    c[0]=d[0]=1e9+1;
    pair<int, long long>up[n+1][L+1];
    for(int i=1; i<=n; i++)
    {
        cin>>d[i]>>c[i];
    }
    stack<pair<long long, long long>>s;
    s.push({c[0], 0});
    for(int i=n; i; i--)
    {
        while(d[i]>=s.top().first)
        {
            s.pop();
        }
        up[i][0].first=s.top().second;
        up[i][0].second=c[s.top().second];
        for(int j=1; j<=L; j++)
        {
            up[i][j].first=up[up[i][j-1].first][j-1].first;
            up[i][j].second=up[i][j-1].second+up[up[i][j-1].first][j-1].second;
        }
        s.push({d[i], i});
    }
    while(q--)
    {
        int idx;
        long long val;
        cin>>idx>>val;
        val-=c[idx];
        if(val<=0)
        {
            cout<<idx<<"\n";
            continue;
        }
        for(int i=L; i>=0; i--)
        {
            if(up[idx][i].second<val)
            {
                val-=up[idx][i].second;
                idx=up[idx][i].first;
            }
        }
        cout<<up[idx][0].first<<"\n";
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 4 ms 448 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 4 ms 600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 33108 KB Output is correct
2 Correct 375 ms 31056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 4 ms 448 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 320 ms 33108 KB Output is correct
9 Correct 375 ms 31056 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 192 ms 18004 KB Output is correct
12 Correct 522 ms 36224 KB Output is correct
13 Correct 433 ms 34244 KB Output is correct
14 Correct 356 ms 33360 KB Output is correct
15 Correct 355 ms 33616 KB Output is correct