Submission #675925

#	Time	Username	Problem	Language	Result	Execution time	Memory
675925		Kubeti	Fountain (eJOI20_fountain)	C++14	30 / 100	1591 ms	3084 KiB

fountain

#include <iostream>
#include <vector>
#include <stack>
#define nmax 100000
using namespace std;
struct fountain{
    int l, d;
} v[nmax + 5];
int ans[nmax+5], n, q;
void build(){
    stack<int> s;
    for(int i=1; i<=n; i++){
        if(s.size() == 0)
            s.push(i);
        else{
            while(!s.empty() && v[i].l > v[s.top()].l){
                ans[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }
    }
    while(!s.empty()){
        ans[s.top()] = -1;
        s.pop();
    }
    
}
int main() {
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>v[i].l>>v[i].d;
    }
    build();
    for(int t=0; t<q; t++){
        int l, i, ok = true;
        cin>>i>>l;
        while(true){
            l -= v[i].d;
            if(l <= 0)
                break;
            if(i == -1){
                ok = false;
                break;
            }
            i = ans[i];
        }
        cout<<max(i, ok)<<endl;
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40