oj.uz

Submission #1008985

# Submission time Handle Problem Language Result Execution time Memory
1008985 2024-06-27T07:27:14 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 420 ms 41668 KB 
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int rad[500001],cap[500001];
array <int,2> sum[500001][21];
vector <int> v;
signed main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>rad[i]>>cap[i];
    for(int i=n;i>=1;i--){
        while(v.size()!=0&&rad[v.back()]<=rad[i]) v.pop_back();
        if(v.size()!=0) sum[i][0]={cap[i],v.back()};
        else sum[i][0]={cap[i],0};
        v.push_back(i);
    }
    for(int k=1;k<=20;k++){
        for(int i=1;i<=n;i++){
            sum[i][k][1]=sum[sum[i][k-1][1]][k-1][1];
            sum[i][k][0]=sum[i][k-1][0]+sum[sum[i][k-1][1]][k-1][0];
        }
    }
    while(q--){
        int i,val;
        cin>>i>>val;
        for(int k=20;k>=0;k--){
            if(val-sum[i][k][0]>0){
                val-=sum[i][k][0];
                i=sum[i][k][1];
            }
        }
        cout<<i<<endl;
    }
    
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 41028 KB Output is correct
2 Correct 304 ms 37148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 270 ms 41028 KB Output is correct
9 Correct 304 ms 37148 KB Output is correct
10 Correct 4 ms 6744 KB Output is correct
11 Correct 162 ms 25772 KB Output is correct
12 Correct 420 ms 41668 KB Output is correct
13 Correct 389 ms 40912 KB Output is correct
14 Correct 337 ms 40620 KB Output is correct
15 Correct 304 ms 40784 KB Output is correct