oj.uz

Submission #754668

# Submission time Handle Problem Language Result Execution time Memory
754668 2023-06-08T10:10:28 Z mraron Fountain (eJOI20_fountain) C++14
100 / 100
 735 ms 38856 KB 
#include<bits/stdc++.h>
using namespace std;
#define xx first 
#define yy second 
using ll = long long ;
int main() {
    int n,q;
    cin>>n>>q;
    vector<pair<int,int>> t(n);
    for(int i=0;i<n;++i) {
        cin>>t[i].xx>>t[i].yy;
    }
    
    t.push_back({1e9+1, 1e9+1});
    
    vector<int> nxt(n+1);
    nxt[n]=n;
    
    vector<int> st={n};
    for(int i=n-1;i>=0;i--) {
        while(!st.empty() && t[st.back()].xx<=t[i].xx) st.pop_back();
        nxt[i]=st.back();
        st.push_back(i);
    }
    
    vector<array<ll,20>> dp(n+1), ends(n+1);
    for(int i=0;i<=n;++i) {
        dp[i][0]=t[i].yy;
        ends[i][0]=i;
    }
    for(int j=1;j<20;++j) {
        for(int i=0;i<=n;++i) {
            dp[i][j]=dp[i][j-1]+dp[nxt[ends[i][j-1]]][j-1];
            ends[i][j]=ends[nxt[ends[i][j-1]]][j-1];
        }
    }
    

    for(int i=0;i<q;++i) {
        int ind;
        ll c;
        cin>>ind>>c;
        ind--;
        for(int j=19;j>=0;j--) {
            if(dp[ind][j]<=c) {
                c-=dp[ind][j];
                ind=(c?nxt[ends[ind][j]]:ends[ind][j]);
            }
        }
        
        cout<<(ind==n?0:ind+1)<<"\n";
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 32892 KB Output is correct
2 Correct 622 ms 33416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 5 ms 696 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 528 ms 32892 KB Output is correct
9 Correct 622 ms 33416 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 299 ms 20648 KB Output is correct
12 Correct 735 ms 38856 KB Output is correct
13 Correct 653 ms 37772 KB Output is correct
14 Correct 569 ms 36916 KB Output is correct
15 Correct 498 ms 37104 KB Output is correct