Submission #1148201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148201		Muhammad_Aneeq	Bouquet (EGOI24_bouquet)	C++20	28 / 100	56 ms	14664 KiB

Main

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <vector>
#warning check the output
using namespace std;
int const N=2e5+10;
int mx[N]={};
void update(int i,int r,int st,int en,int val)
{
    if (st==en)
    {
        mx[i]=val;
        return;
    }
    int mid=(st+en)/2;
    if (r<=mid)
        update(i*2,r,st,mid,val);
    else
        update(i*2+1,r,mid+1,en,val);
    mx[i]=max(mx[i*2],mx[i*2+1]);
}
int get(int i,int st,int en,int l,int r)
{
    if (st>=l&&en<=r)
        return mx[i];
    if (st>r||en<l)
        return 0;
    int mid=(st+en)/2;
    return max(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}

inline void solve()
{
    int n;
    cin>>n;
    int l[n],r[n];
    for (int i=0;i<n;i++)
    {
        cin>>l[i]>>r[i];
        l[i]=max(0,i-l[i]);
        r[i]=min(n-1,i+r[i]);
    }
    int dp[n]={};
    vector<int>ve[n]={};
    for (int i=0;i<n;i++)
        ve[r[i]].push_back(i);
    for (int i=0;i<n;i++)
    {
        int z=get(1,0,n-1,0,l[i]-1);
        dp[i]=z+1;
        for (auto j:ve[i])
            update(1,j,0,n-1,dp[j]);
    }
    cout<<mx[1]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

Main.cpp:10:2: warning: #warning check the output [-Wcpp]
   10 | #warning check the output
      |  ^~~~~~~

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