oj.uz

Submission #1008981

# Submission time Handle Problem Language Result Execution time Memory
1008981 2024-06-27T07:23:35 Z m5588ohammed Fountain (eJOI20_fountain) C++14
100 / 100
 423 ms 45596 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 3 ms 4700 KB Output is correct
3 Correct 4 ms 6744 KB Output is correct
4 Correct 4 ms 6804 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 5 ms 6824 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 43936 KB Output is correct
2 Correct 342 ms 40132 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 3 ms 4700 KB Output is correct
3 Correct 4 ms 6744 KB Output is correct
4 Correct 4 ms 6804 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 5 ms 6824 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 270 ms 43936 KB Output is correct
9 Correct 342 ms 40132 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 145 ms 27472 KB Output is correct
12 Correct 423 ms 45596 KB Output is correct
13 Correct 405 ms 44500 KB Output is correct
14 Correct 299 ms 43600 KB Output is correct
15 Correct 318 ms 43808 KB Output is correct