Submission #1072506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072506		ivaziva	Bouquet (EGOI24_bouquet)	C++14	100 / 100	139 ms	36436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

long long n;
long long l[MAXN],r[MAXN];
long long dp[MAXN][2];
set<pair<long long,long>> cuvamo[MAXN];
long long seg[MAXN*4];

void update(long long node,long long ll,long long rr,long long pos,long long val)
{
    if (ll==rr) seg[node]=val;
    else
    {
        long long mid=(ll+rr)/2;
        if (pos<=mid) update(2*node,ll,mid,pos,val);
        else update(2*node+1,mid+1,rr,pos,val);
        seg[node]=max(seg[2*node],seg[2*node+1]);
    }
}

long long query(long long node,long long ll,long long rr,long long a,long long b)
{
    if (a>b) return 0;
    if (ll==a and rr==b) return seg[node];
    long long mid=(ll+rr)/2;
    return max(query(2*node,ll,mid,a,min(b,mid)),query(2*node+1,mid+1,rr,max(a,mid+1),b));
}

int main()
{
    cin>>n;
    for (long long i=1;i<=n;i++) cin>>l[i]>>r[i];
    dp[0][0]=dp[0][1]=0;
    for (long long i=1;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        for (pair<long long,long long> par:cuvamo[i])
        {
            long long vrednost=par.first;
            long long pozicija=par.second;
            update(1,1,n,pozicija,vrednost);
        }
        long long levo=i-l[i]-1;
        dp[i][1]=query(1,1,n,1,levo)+1;
        long long desno=i+r[i]+1;
        if (desno<=n) cuvamo[desno].insert({dp[i][1],i});
    }
    cout<<max(dp[n][0],dp[n][1]);
}

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