Submission #1148201

#TimeUsernameProblemLanguageResultExecution timeMemory
1148201Muhammad_AneeqBouquet (EGOI24_bouquet)C++20
28 / 100
56 ms14664 KiB
/*
بسم الله الرحمن الرحيم
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
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...