Submission #675957

#	Time	Username	Problem	Language	Result	Execution time	Memory
675957		Kubeti	Fountain (eJOI20_fountain)	C++14	60 / 100	323 ms	5148 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], smen[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;
    }
    if(n <= 2000){
        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;
        }
    }
    else{
        for(int i=1; i<=n; i++){
            smen[i] = smen[i-1] + v[i].d;
        }
        for(int t=0; t<q; t++){
            int l, i;
            cin>>i>>l;
            int st=i, dr=n+1;
            while(st<dr){
                int mid = (st+dr)/2;
                if(smen[mid] - smen[i-1] < l)
                    st = mid + 1;
                else dr = mid;
            }
            if(dr == n+1)
                cout<<0<<'\n';
            else cout<<dr<<'\n';
        }
    }
}

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