oj.uz

Submission #754667

# Submission time Handle Problem Language Result Execution time Memory
754667 2023-06-08T10:06:31 Z mraron Fountain (eJOI20_fountain) C++14
0 / 100
 474 ms 35744 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=nxt[ends[ind][j]];
            }
        }
        
        cout<<(ind==n?0:ind+1)<<"\n";
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 474 ms 35744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -