Submission #1038534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038534		mkkkkkkkk	Fountain (eJOI20_fountain)	C++14	100 / 100	404 ms	41108 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

int cap[200001],parent[200001],ps[200001],depth[200001];
vector<int> adj[200001];
int sp[21][200001];
int logg[200001];
void dfs(int i,int par,int d)
{
    ps[i]+=ps[par];
    depth[i]=d;
    for(auto it : adj[i])
    {
        if(par!=it)
        {
            dfs(it,i,d+1);
        }
    }
}

#include <bits/extc++.h>
using namespace __gnu_pbds;

typedef tree<pair<int,int>,null_type,less<pair<int,int>>, rb_tree_tag,
                tree_order_statistics_node_update> ost;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    ost st;
    vector<pair<int,int>> vec;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        cap[i]=b;
        ps[i]=b;
        vec.push_back({a,-i});
    }
    sort(vec.begin(),vec.end());
    for(int j=n;j>0;j--)
    {
        int a=vec[j-1].first,i=-(vec[j-1].second);
        st.insert({i,a});
        int br=0;
        int brr=st.order_of_key({i,a});

        if(brr==st.size()-1)
        {
            parent[i]=0;
            adj[0].push_back(i);
            adj[i].push_back(0);
        }
        else
        {

            br=(*st.find_by_order(brr+1)).first;
            adj[br].push_back(i);
            adj[i].push_back(br);
            parent[i]=br;
        }
    }
    dfs(0,0,0);
    sp[0][0]=-1;
    for(int i=1;i<=n;i++)
    {
        sp[0][i]=parent[i];
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(sp[i-1][j]==-1)
            sp[i][j]=-1;
            else
                sp[i][j]=sp[i-1][sp[i-1][j]];
        }
    }
    for(int i=1,j=0;i<=200000;i=i*2,j++)
    {
        logg[i]=j;
    }
    for(;q>0;q--)
    {
        int a,b;
        cin>>a>>b;
        if(cap[a]>=b)
        {
            cout<<a<<"\n";
            continue;
        }
        int l=0,r=depth[a]-1;
        int m=(l+r)/2;
        for(;l<=r;m=(l+r)/2)
        {
            int br=m,br2=a;
            for(int brr=0;br>0;br=br>>1,brr++)
            {
                if(br&1==1)
                {
                    br2=sp[brr][br2];
                }
            }
            br2=parent[br2];
            if(ps[a]-ps[br2]<b)
            {
                l=m+1;
            }
            else
                r=m-1;
        }
        int br=m,br2=a;
            for(int brr=0;br>0;br=br>>1,brr++)
            {
                if(br&1==1)
                {
                    br2=sp[brr][br2];
                }
            }
            br2=parent[br2];
            cout<<br2<<"\n";
    }

    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if(brr==st.size()-1)
      |            ~~~^~~~~~~~~~~~~
fountain.cpp:104:24: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  104 |                 if(br&1==1)
      |                       ~^~~
fountain.cpp:120:24: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  120 |                 if(br&1==1)
      |                       ~^~~

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