Submission #650712

#	Time	Username	Problem	Language	Result	Execution time	Memory
650712		sofija6	Fountain (eJOI20_fountain)	C++14	100 / 100	1095 ms	50204 KiB

fountain

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define llinf 1000000000000
#define logn 20
using namespace std;
ll d[MAXN],c[MAXN],sum[MAXN][logn],up[MAXN][logn];
stack<pair<ll,ll> > s;
vector<ll> G[MAXN];
vector<bool> V(MAXN);
void DFS(ll i,ll par)
{
    V[i]=true;
    up[i][0]=par;
    sum[i][0]=(i!=par)*c[par];
    for (ll j=1;j<logn;j++)
    {
        up[i][j]=up[up[i][j-1]][j-1];
        sum[i][j]=sum[i][j-1]+sum[up[i][j-1]][j-1];
    }
    for (ll next : G[i])
    {
        if (!V[next])
            DFS(next,i);
    }
}
pair<ll,ll> Check(ll u,ll x)
{
    ll cur=c[u];
    for (ll i=logn-1;i>=0;i--)
    {
        if ((1<<i)<=x)
        {
            x-=(1<<i);
            cur+=sum[u][i];
            u=up[u][i];
        }
    }
    return {cur,u};
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,q,r,v;
    cin >> n >> q;
    for (ll i=1;i<=n;i++)
        cin >> d[i] >> c[i];
    d[n+1]=llinf;
    c[n+1]=llinf;
    s.push({llinf,n+1});
    for (ll i=n;i>=1;i--)
    {
        while (s.top().first<=d[i])
            s.pop();
        G[i].push_back(s.top().second);
        G[s.top().second].push_back(i);
        s.push({d[i],i});
    }
    for (ll i=n+1;i>=1;i--)
    {
        if (!V[i])
            DFS(i,i);
    }
    while (q--)
    {
        cin >> r >> v;
        if (v<=c[r])
        {
            cout << r << "\n";
            continue;
        }
        ll l=1,rr=n+1,mid,ans;
        while (l<=rr)
        {
            mid=(l+rr)/2;
            auto p=Check(r,mid);
            if (p.first>=v)
            {
                ans=p.second;
                rr=mid-1;
            }
            else
                l=mid+1;
        }
        cout << ans%(n+1) << "\n";
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:85:25: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |         cout << ans%(n+1) << "\n";
      |                         ^

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