oj.uz

Submission #431592

# Submission time Handle Problem Language Result Execution time Memory
431592 2021-06-17T13:23:35 Z Dakto Fountain (eJOI20_fountain) C++17
0 / 100
 113 ms 26732 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n,q;
    cin>>n>>q;
    vector<long long> d(n+1),c(n+1);
    for(int i=1; i<=n; i++) cin>>d[i]>>c[i];
    vector<int> root(n+1,0), tot(n+1,0);
    vector<vector<int>> jmp(n+1);
    d[0]=c[0]=2*1e9;
    stack<int> s;
    s.push(0);
    for(int i=n; i>0; i--){
        while(d[s.top()]<=d[i]) s.pop();
        root[i]=s.top();
        tot[i]=tot[s.top()]+c[i];
        jmp[i].push_back(root[i]);
        s.push(i);
    }
    for(int i=0; i<log2(2*n); i++){
        jmp[0].push_back(0);
        for(int j=0; j<n; j++) 
            jmp[j].push_back(jmp[jmp[j][i]][i]);
    }

    for(int i=0; i<q; i++){
        long long r,v;
        cin>>r>>v;
        long long goal=tot[r]-v;
        for(int j=log2(2*n); j>=0; j--){
            if(tot[jmp[r][j]]>goal) r=jmp[r][j];

        }
        cout<<r<<endl;
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Runtime error 2 ms 716 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 26732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Runtime error 2 ms 716 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -