Submission #1157355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157355		andrei_boaca	Fountain (eJOI20_fountain)	C++20	0 / 100	292 ms	32512 KiB

fountain

#include <bits/stdc++.h>
#define int long long

using namespace std;

long long binary_first_that(long long st, long long dr, const function<bool(long long)> &f)
{
    long long mij;
    while(st <= dr)
    {
        mij = (st+dr)/2;
        if(f(mij)) dr = mij - 1;
        else st = mij + 1;
    }
    return dr+1;
}

int d[100005],v[100005];
vector<int> dsort;
int up[100005][19];
int sum[100005][19];

int upWith(int node, int x)
{
    for(; x; x ^= (x&-x))
        node = up[node][__builtin_ctzll(x)];
    return node;
}

int sumWith(int node, int x)
{
    int res = 0;
    for(; x; x ^= (x&-x))
    {
        res += sum[node][__builtin_ctzll(x)];
        node = up[node][__builtin_ctzll(x)];
    }
    return res + v[node];
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,q; cin>>n>>q;
    for(int i=1; i<=n; ++i)
    {
        cin>>d[i]>>v[i];
        dsort.push_back(d[i]);
    }
//    sort(dsort.begin(), dsort.end());
//    dsort.erase(unique(dsort.begin(), dsort.end()), dsort.end());
//    for(int i=1; i<=n; ++i)
//        d[i] = lower_bound(dsort.begin(), dsort.end(), d[i]) - dsort.begin() + 1;
    d[n+1] = 2e9;
    v[n+1] = 2e9;
    stack<int> st({n+1});
    for(int i=n; i>0; --i)
    {
        while(d[st.top()] <= d[i])
            st.pop();
        int father = st.top();
        up[i][0] = father;
        sum[i][0] = v[father];
        st.push(i);
//        cout<<i<<' '<<father<<'\n';
    }
    up[n+1][0] = n+1;
    sum[n+1][0] = 0;
    for(int i=1; i<=18; ++i)
        for(int j=1; j<=n; ++j)
        {
            up[j][i] = up[up[j][i-1]][i-1];
            sum[j][i] = sum[j][i-1] + sum[up[j][i-1]][i-1];
        }
    while(q--)
    {
        int node, val; cin>>node>>val;
        int dist = binary_first_that(0, n, [&node,&val](int x){return sumWith(node,x) >= val;});
        int ans = upWith(node, dist);
        cout<<(ans == n+1 ? 0 : ans)<<'\n';
    }
    return 0;
}
/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

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