oj.uz

Submission #1020126

# Submission time Handle Problem Language Result Execution time Memory
1020126 2024-07-11T15:19:39 Z biserailieva Fountain (eJOI20_fountain) C++14
100 / 100
 499 ms 42948 KB 
#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 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 2 ms 2512 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2884 KB Output is correct
7 Correct 4 ms 4840 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 39612 KB Output is correct
2 Correct 357 ms 38596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 2 ms 2512 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2884 KB Output is correct
7 Correct 4 ms 4840 KB Output is correct
8 Correct 348 ms 39612 KB Output is correct
9 Correct 357 ms 38596 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct
11 Correct 182 ms 25500 KB Output is correct
12 Correct 499 ms 42948 KB Output is correct
13 Correct 416 ms 41676 KB Output is correct
14 Correct 381 ms 42320 KB Output is correct
15 Correct 357 ms 41040 KB Output is correct