Submission #588450

#	Time	Username	Problem	Language	Result	Execution time	Memory
588450		berr	Fountain (eJOI20_fountain)	C++17	0 / 100	33 ms	14316 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
vector<array<int, 2>> x[100005];
vector<array<int, 2>> con[100005];
vector<int> pl(100005), type(100005);

int val(int ri, int vi)
{
    if(pl[ri]==0) return 0;
    return x[type[ri]][pl[ri]-1][0];
}

int query(int ri, int vi)
{
    if(ri==1e9) return 0;

    vi+=val(ri, vi);

    if(vi>x[type[ri]][x[type[ri]].size()-1][0])
    {
        if(con[ri].size()==0)
        {
            return 0;
        }
        else
        {
            vi-=x[type[ri]][x[type[ri]].size()-1][0];
            return query(con[ri][0][1], vi);
        }
    }

    

    int s=0;

    for(int i=17; i>=0; i--)
    {
        if(s+(1<<i)<x[type[ri]].size()&&x[type[ri]][s+(1<<i)][0]<vi)
        s+=(1<<i);
    }
    if(x[type[ri]][s][0]<=vi) s++;
    return x[type[ri]][s][1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; cin>>n>>q;
  
    vector<int> a(n+1), b(n+1);
    for(int i=1; i<=n; i++)
    {
        cin>>a[i]>>b[i];
    }

    int cnt=0;
    vector<int> la(1001), bi(1001);
    la[a[n]]=n;

    for(int i=n-1; i>=1; i--)
    {
        int ind=1e9;
        for(int l=a[i]+1; l<=1000; l++)
        {
            if(la[l]!=0)
                ind=min(ind, la[l]);
        }
        la[a[i]]=i;

        bi[i]=ind;
        
    }

    for(int i=1; i<=n; i++)
    {
        if(type[i]==0)
        {
            cnt++;
            type[i]=cnt;
            x[cnt].push_back({b[i], i});
            if(bi[i]!=1e9)
             {   
                if(type[bi[i]]!=0) con[i].push_back({type[bi[i]], bi[i]});
                else x[cnt].push_back({b[bi[i]], bi[i]}),type[bi[i]]=cnt;
            }
        }

        else
        {
       
            if(bi[i]!=1e9)
            {
                 if(type[bi[i]]!=0) con[i].push_back({type[bi[i]], bi[i]});   
                 else { x[type[i]].push_back({b[bi[i]], bi[i]}),type[bi[i]]=type[i];}
            }


        }
    }

    for(int i=1; i<=cnt; i++)
    {
        pl[x[i][0][1]]=0;

        for(int l=1; l<x[i].size(); l++)
        {
            x[i][l][0]+=x[i][l-1][0];
            pl[x[i][l][1]]=l;
        }




    }





    while(q--)
    {
        int ri, vi; cin>>ri>>vi;

        cout<<query(ri, vi)<<"\n";
    }
   


}

Compilation message (stderr)

fountain.cpp: In function 'int query(int, int)':
fountain.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(s+(1<<i)<x[type[ri]].size()&&x[type[ri]][s+(1<<i)][0]<vi)
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int l=1; l<x[i].size(); l++)
      |                      ~^~~~~~~~~~~~

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