oj.uz

Submission #650712

# Submission time Handle Problem Language Result Execution time Memory
650712 2022-10-14T21:38:35 Z sofija6 Fountain (eJOI20_fountain) C++14
100 / 100
 1095 ms 50204 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 4 ms 3084 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 46680 KB Output is correct
2 Correct 769 ms 43596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 4 ms 3084 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 716 ms 46680 KB Output is correct
9 Correct 769 ms 43596 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 249 ms 25704 KB Output is correct
12 Correct 1095 ms 50204 KB Output is correct
13 Correct 430 ms 44736 KB Output is correct
14 Correct 248 ms 43272 KB Output is correct
15 Correct 143 ms 43880 KB Output is correct