Submission #1233019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233019		erering	Fountain (eJOI20_fountain)	C++20	100 / 100	142 ms	36704 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define int long long
const int N=1e5+5,inf=2e9,MOD=1e9+7;
int nxt[N];
pair<int,int> up[N][20];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<N;i++){
        for(int j=0;j<20;j++)up[i][j]={N-1,inf};
    }
    int n,q; cin>>n>>q;
    int d[n],c[n];
    for(int i=0;i<n;i++){
        cin>>d[i]>>c[i];
    }
    deque<pair<int,int>> dq;
    dq.pb({N-1,inf});
    for(int i=n-1;i>=0;i--){
        while(dq.front().second<=d[i])dq.pop_front();
        nxt[i]=dq.front().first;
        dq.push_front({i,d[i]});
        up[i][0]={nxt[i],c[i]};
        for(int j=1;j<20;j++){
            up[i][j]=up[up[i][j-1].first][j-1];
            up[i][j].second+=up[i][j-1].second;
        }
    }
    while(q--){
        int r,v; cin>>r>>v;
        r--;
        for(int j=19;j>=0;j--){
            if(up[r][j].second<v){
                v-=up[r][j].second;
                r=up[r][j].first;
            }
        }
        cout<<(r==N-1?0:r+1)<<endl;
    }
}

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