oj.uz

Submission #640847

# Submission time Handle Problem Language Result Execution time Memory
640847 2022-09-15T10:56:35 Z Urvuk3 Fountain (eJOI20_fountain) C++17
100 / 100
 461 ms 38376 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 32252 KB Output is correct
2 Correct 328 ms 29912 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 312 ms 32252 KB Output is correct
9 Correct 328 ms 29912 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 137 ms 20784 KB Output is correct
12 Correct 461 ms 38376 KB Output is correct
13 Correct 316 ms 37948 KB Output is correct
14 Correct 219 ms 37316 KB Output is correct
15 Correct 168 ms 37944 KB Output is correct