Submission #431594

#	Time	Username	Problem	Language	Result	Execution time	Memory
431594		Dakto	Fountain (eJOI20_fountain)	C++17	100 / 100	1251 ms	24804 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n,q;
    cin>>n>>q;
    vector<long long> d(n+1),c(n+1);
    for(int i=1; i<=n; i++) cin>>d[i]>>c[i];
    vector<int> root(n+1,0), tot(n+1,0);
    vector<vector<int>> jmp(n+1);
    d[0]=c[0]=2*1e9;
    stack<int> s;
    s.push(0);
    for(int i=n; i>0; i--){
        while(d[s.top()]<=d[i]) s.pop();
        root[i]=s.top();
        tot[i]=tot[s.top()]+c[i];
        jmp[i].push_back(root[i]);
        s.push(i);
    }
    for(int i=0; i<log2(2*n); i++){
        jmp[0].push_back(0);
        for(int j=1; j<=n; j++) 
            jmp[j].push_back(jmp[jmp[j][i]][i]);
    }

    for(int i=0; i<q; i++){
        long long r,v;
        cin>>r>>v;
        long long goal=tot[r]-v;
        for(int j=log2(2*n); j>=0; j--){
            if(tot[jmp[r][j]]>goal) r=jmp[r][j];

        }
        cout<<r<<endl;
    }
}

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