Submission #641519

#	Time	Username	Problem	Language	Result	Execution time	Memory
641519		Adnanboi	Fountain (eJOI20_fountain)	C++17	30 / 100	1582 ms	3588 KiB

fountain

#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 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40