oj.uz

Submission #641519

# Submission time Handle Problem Language Result Execution time Memory
641519 2022-09-16T21:34:13 Z Adnanboi Fountain (eJOI20_fountain) C++17
30 / 100
 1500 ms 3588 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 > b) 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 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 3 ms 368 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 3588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 3 ms 368 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Execution timed out 1582 ms 3588 KB Time limit exceeded
9 Halted 0 ms 0 KB -