oj.uz

Submission #431594

# Submission time Handle Problem Language Result Execution time Memory
431594 2021-06-17T13:25:29 Z Dakto Fountain (eJOI20_fountain) C++17
100 / 100
 1251 ms 24804 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=1; 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 304 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 4 ms 484 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 8 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 20928 KB Output is correct
2 Correct 885 ms 21064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 304 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 4 ms 484 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 784 ms 20928 KB Output is correct
9 Correct 885 ms 21064 KB Output is correct
10 Correct 7 ms 432 KB Output is correct
11 Correct 416 ms 12996 KB Output is correct
12 Correct 1251 ms 24804 KB Output is correct
13 Correct 946 ms 23892 KB Output is correct
14 Correct 799 ms 23200 KB Output is correct
15 Correct 693 ms 23508 KB Output is correct