oj.uz

Submission #641520

# Submission time Handle Problem Language Result Execution time Memory
641520 2022-09-16T21:36:07 Z Adnanboi Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 5784 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> nums;
vector<int> pref;
int n;

/*

5 1
1 4
2 4
3 5
4 5
5 5
1 17
{4,4,5, 5, 5}
{4,8,13,18,23}
output : 4

*/

int binarysearch(int index, int value){
    int l = index, r = n;
    while(l<=r){
        int mid = (l+r) / 2;
        if(pref[mid] - pref[index-1] > value) r = mid - 1;
        else if(pref[mid] - pref[index-1] < value) l = mid + 1;
        else if(pref[mid] - pref[index-1] == value){
            return mid;
        }
    }
    return l;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin>>n>>q;
    nums = vector<int>(n+1);
    pref = vector<int>(n+1,0);
    vector<int> diam(n+1);
    vector<int> dfs(n+1);
    int maximum = 0;
    bool check = true;
    for(int i = 1; i <= n; i++){
        int a,b;
        cin>>a>>b;
        diam[i] = a;
        maximum = max(maximum,a);
        if(maximum > a) check = false;
        nums[i]=b;
        if(i==1) pref[i]=nums[i];
        else pref[i] = pref[i-1] + nums[i];
    }
    if(!check){
    stack<int> s;
    s.push(n);
    dfs[n] = 0;
    for(int i = n-1; i >= 1; i--){
        while(!s.empty() && diam[i]>=diam[s.top()]) s.pop();
        if(s.empty()) dfs[i] = 0;
        else dfs[i] = s.top();
        s.push(i);
    }
    }
    //for(int i = 1; i <= n; i++){
    //    cout<<i<<" : "<<dfs[i]<<'\n';
    //}
    
    while(q--){
        int a,b;
        cin>>a>>b;
        int i = a;
        if(check) cout<<(binarysearch(a,b)>=n+1 ? 0 : binarysearch(a,b))<<'\n';
        else{
            while(b>0){
                if(i==0) break;
                b -= nums[i];
                if(b<=0) break;
                i = dfs[i]; 
            }
            cout<<i<<'\n';
        }
    }
    
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3648 KB Output is correct
2 Correct 71 ms 5348 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 62 ms 3648 KB Output is correct
9 Correct 71 ms 5348 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 811 ms 3472 KB Output is correct
12 Correct 121 ms 5784 KB Output is correct
13 Execution timed out 1568 ms 4464 KB Time limit exceeded
14 Halted 0 ms 0 KB -