Submission #1155986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155986		andrei_n	Fountain (eJOI20_fountain)	C++20	0 / 100	289 ms	31912 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][18];
int sum[100005][18];
int aib[100005];
int last[100005];

void update(int p, int x)
{
    for(; p<100005; p+=(p&-p))
        aib[p] += x;
}

int query(int p)
{
    int res = 0;
    for(; p; p^=(p&-p))
        res += aib[p];
    return res;
}

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] = 100001;
    v[n+1] = 999999999;
    update(d[n+1], 1);
    last[100001] = n+1;
    for(int i=n; i>0; --i)
    {
        int father = binary_first_that(d[i]+1, d[n+1], [&i](int x){return bool(query(x) - query(d[i]));});
        up[i][0] = last[father];
        sum[i][0] = v[last[father]];
        update(d[i], 1);
        last[d[i]] = i;
    }
    for(int i=1; (1<<i) < n; ++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-1, [&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