Submission #840851

#	Time	Username	Problem	Language	Result	Execution time	Memory
840851		raul2008487	Fountain (eJOI20_fountain)	C++17	100 / 100	563 ms	37616 KiB

fountain

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define F first
#define S second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
#define inf 0x3F3F3F3F
using namespace std;
const int mod = 1e9+7;
const int sz = 1e5+5;
const ll oo = 1000000000000000005;
ll st[20][sz], water[20][sz];
void solve(){
    ll n,q,i,j,len;
    cin>>n>>q;
    deque<pair<ll,ll>> dq;
    for(i=1;i<=n;i++){
        cin>>len>>water[0][i];
        while(!dq.empty() && len > dq.front().first){
            st[0][dq.front().second]=i;
            dq.pop_front();
        }
        dq.push_front({len,i});
    }
    for(i=1;i<20;i++){
        for(j=1;j<=n;j++){
            st[i][j] = st[i-1][st[i-1][j]];
            water[i][j] = water[i-1][j] + water[i-1][st[i-1][j]];
        }
    }
    while(q--){
        ll ix, g;
        cin>>ix>>g;
        for(i=19;i>=0;i--){
            if(water[i][ix] < g){
                g-=water[i][ix];
                ix = st[i][ix];
            }
        }
        cout << ix << endl;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }

}
/*
2 1
1 2 5
4
2
1 2
*/

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