Submission #1095497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095497		vjudge1	Bouquet (EGOI24_bouquet)	C++17	100 / 100	112 ms	17748 KiB

Main

#include<bits/stdc++.h>
#define N 200005
#define pb push_back

using namespace std;

int v[2*N],n;

inline void update(int ind,int x)
{
    ind+=n;
    v[ind]=x;
    for(;ind>1;ind/=2)
        v[ind/2]=max(v[ind],v[ind^1]);
    return;
}

inline int query(int l,int r)
{
    int ans=0;
    l+=n;
    r+=n;
    for(;l<r;l/=2,r/=2)
    {
        if(l%2)
            ans=max(ans,v[l++]);
        if(r%2)
            ans=max(ans,v[--r]);
    }
    return ans;
}

int32_t main()
{
    cin>>n;
    vector<int> x[n+1];
    int l[n],r[n],dp[N];
    for(int i=0;i<n;i++) cin>>l[i]>>r[i];
    int maxim[N],ans=0;
    memset(maxim,0,sizeof(maxim));
    for(int i=n-1;i>=0;i--)
    {
        maxim[i]=maxim[i+1];
        for(int j=0;j<x[i+1].size();j++)
        {
            maxim[x[i+1][j]]=max(dp[x[i+1][j]],maxim[x[i+1][j]]);
            update(x[i+1][j],maxim[x[i+1][j]]);
            //cout<<maxim[x[i+1][j]]<<endl;
        }
        //cout<<i+r[i]<<" "<<n-1<<endl;
        if(i+r[i]+1<=n-1){
            //cout<<query(5,5)<<" "<<v[n+5]<<"OK\n";
            dp[i]=query(i+r[i]+1,n)+1;
        }
        else
            dp[i]=1;
        ans=max(ans,dp[i]);
        if(i-l[i]<0)
            continue;
        x[i-l[i]].pb(i);
    }
    
    /*for(int i=0;i<n;i++)
    {
        cout<<dp[i]<<" ";
    }
    cout<<endl;*/
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j=0;j<x[i+1].size();j++)
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30