Submission #1157357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157357		andrei_n	Fountain (eJOI20_fountain)	C++20	100 / 100	491 ms	34308 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, cnode = node;
    for(; x; x ^= (x&-x))
    {
        res += sum[node][__builtin_ctzll(x)];
        node = up[node][__builtin_ctzll(x)];
    }
    return res + v[cnode];
}

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] = 999999999;
    v[n+1] = 999999999;
    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+1; ++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;
        if(val <= v[node])
        {
            cout<<node<<'\n';
            continue;
        }
        int dist = binary_first_that(0, n, [&node,&val](int x){return sumWith(node,x) >= val;});
//        cout<<sumWith(2, 1)<<' ';
        int ans = upWith(node, dist);
        cout<<(ans == n+1 ? 0 : ans)<<'\n';
    }
    return 0;
}
/*
5 1
1 7
2 3
3 10
4 4
5 4
2 18
*/

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