oj.uz

Submission #1009010

# Submission time Handle Problem Language Result Execution time Memory
1009010 2024-06-27T07:56:31 Z Almonther Fountain (eJOI20_fountain) C++
100 / 100
 131 ms 45776 KB 
#include <bits/stdc++.h>
 
#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
const ll maxn=1000001;
ll n,q;
ll arr[maxn],val[maxn];
ll f[maxn][22][2];
ll bigger[maxn];
void make_spars(ll x){
    if(x==0){
        for(int i=1;i<=n;i++){
            f[i][x][0]=val[i];
            f[i][x][1]=bigger[i];
        }
    }
    else{
        for(int i=1;i<=n;i++){
            f[i][x][0]=f[i][x-1][0]+f[f[i][x-1][1]][x-1][0];
            f[i][x][1]=f[f[i][x-1][1]][x-1][1];
        }
    }
}
void solve(){
    cin>>n>>q;
    vector<ll>v;
    for(int i=1;i<=n;i++){
        cin>>arr[i]>>val[i];
    }
    for(int i=n;i>=1;i--){
        while(v.size()&&arr[v.back()]<=arr[i]) v.pop_back();
        if(v.size()) bigger[i]=v.back();
        else bigger[i]=0;
        v.push_back(i);
    }
    for(int i=0;i<=21;i++) make_spars(i);
    while(q--){
        ll a,b;
        cin>>a>>b;
        ll idx=21;
        while(idx>=0){
            if(a==0) break;
            if(b-f[a][idx][0]>0&&f[a][idx][0]!=0){
                b-=f[a][idx][0];
                a=f[a][idx][1];
            }
            idx--;
        }
        co a<<'\n';
    }
}
 
int main()
{
    suiii
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 43212 KB Output is correct
2 Correct 80 ms 41168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 79 ms 43212 KB Output is correct
9 Correct 80 ms 41168 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 42 ms 29976 KB Output is correct
12 Correct 131 ms 45776 KB Output is correct
13 Correct 99 ms 45040 KB Output is correct
14 Correct 71 ms 44772 KB Output is correct
15 Correct 60 ms 44816 KB Output is correct