Submission #466506

#	Time	Username	Problem	Language	Result	Execution time	Memory
466506		FulopMate	Fountain (eJOI20_fountain)	C++17	100 / 100	698 ms	38128 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(c) (c).begin(), (c).end()
#define MIN(a, b) ((a) = min((a), (b)))
#define MAX(a, b) ((a) = max((a), (b)))

const ll MOD = 1e9+7;
const int abc = 'z'-'a'+1;

int n, q;
vector<ll> d, c;
vector<ll> p;
vector<array<pair<ll,int>, 19>> v;
// v[i][j] = i. medencebol indulva 2^j-t lemenve (a faban) {mennyi viz kell, melyik medence}
// v[n][barmi] = {1e9+1, n};

int query(int i, ll w){
    if(w <= c[i]) return i;
    int j = 0;
    while(v[i][j].first < w)j++;
    j--;
    return query(v[i][j].second, w-v[i][j].first);
}

void solve(){
    cin>>n>>q;
    d.resize(n); c.resize(n);
    for(int i = 0; i < n; i++){
        cin>>d[i]>>c[i];
    }
    p.assign(n, 0);
    stack<int> s;
    for(int i = n-1; i >= 0; i--){
        while(!s.empty() && d[s.top()] <= d[i]){
            s.pop();
        }
        if(s.empty()) p[i] = n;
        else p[i] = s.top();
        s.push(i);
    }
    v.assign(n+1, array<pair<ll,int>, 19>());
    for(int i = 0; i < 19; i++){
        v[n][i] = {1e17+1, n};
    }
    for(int i = n-1; i >= 0; i--){
        if(p[i] == n){
            for(int j = 0; j < 19; j++){
                v[i][j] = {1e17+1, n};
            }
            continue;
        }
        v[i][0] = {c[i], p[i]};
        for(int j = 1; j < 19; j++){
            if(v[i][j-1].second == n){
                v[i][j] = {1e17+1, n};
                continue;
            }
            if(v[ v[i][j-1].second ][j-1].second == n){
                v[i][j] = {1e17+1, n};
                continue;
            }
            v[i][j].first = v[i][j-1].first + v[ v[i][j-1].second ][j-1].first;
            v[i][j].second = v[ v[i][j-1].second ][j-1].second;
        }
    }
    while(q--){
        int a, b; cin>>a>>b; a--;
        int r = query(a, b);
        cout<<(r+1)%(n+1)<<endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t;
    _t = 1;
    while(_t--){
        solve();
    }
    return 0;
}

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