Submission #640847

#	Time	Username	Problem	Language	Result	Execution time	Memory
640847		Urvuk3	Fountain (eJOI20_fountain)	C++17	100 / 100	461 ms	38376 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(niz) { cerr<<#niz<<"="; for(auto _i:niz) cerr<<_i<<" "; cerr<<endl; }

void Solve(){
    int N,Q; cin>>N>>Q;
    vector<pair<int,ll>> a(N+1); a[0]={INF,INF};
    for(int i=1;i<=N;i++){
        cin>>a[i].fi>>a[i].se;
    }
    stack<int> s;
    vector<vector<int>> anc(N+1,vector<int>(21,0));
    vector<vector<ll>> sum(N+1,vector<ll>(21,0));
    for(int i=1;i<=N;i++){
        while(!s.empty() && a[s.top()].fi<a[i].fi){
            anc[s.top()][0]=i;
            sum[s.top()][0]=a[i].se;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty() && a[s.top()].fi<a[0].fi){
        anc[s.top()][0]=0;
        sum[s.top()][0]=a[0].se;
        s.pop();
    }
    sum[0][0]=INF;
    for(int deg=1;deg<=20;deg++){
        for(int i=0;i<=N;i++){
            anc[i][deg]=anc[anc[i][deg-1]][deg-1];
            sum[i][deg]=sum[i][deg-1]+sum[anc[i][deg-1]][deg-1];
        }
    }
    /*
    for(int i=0;i<=N;i++){
        for(int deg=0;deg<=2;deg++){
            cerr<<"anc["<<i<<"]["<<deg<<"]="<<anc[i][deg]<<endl;
            cerr<<"sum["<<i<<"]["<<deg<<"]="<<sum[i][deg]<<endl;
        }
        cerr<<endl;
    }
    */
    while(Q--){
        int idx; ll litri; cin>>idx>>litri;
        if(a[idx].se>=litri){
            cout<<idx<<endl;
            continue;
        }
        int v=idx;
        ll fontane=a[idx].se;
        for(int deg=20;deg>=0;deg--){
            if(fontane+sum[v][deg]<litri){
                fontane+=sum[v][deg];
                v=anc[v][deg];
            }
        }
        cout<<anc[v][0]<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

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