Submission #737167

#	Time	Username	Problem	Language	Result	Execution time	Memory
737167		alexdd	Financial Report (JOI21_financial)	C++17	0 / 100	4050 ms	6176 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n,d;
int a[300005];
int dp[300005];
int posmic[300005];
int posmare[300005];
int pozs[300005];
deque<int> dqmic;
deque<int> dqmare;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        while(!dqmic.empty() && a[dqmic.back()]>=a[i])
            dqmic.pop_back();
        if(!dqmic.empty())
            posmic[i] = dqmic.back();
        else
            posmic[i] = 0;
        dqmic.push_back(i);

        while(!dqmare.empty() && a[dqmare.back()]<=a[i])
            dqmare.pop_back();
        if(!dqmare.empty())
            posmare[i] = dqmare.back();
        else
            posmare[i] = 0;
        dqmare.push_back(i);
        //cout<<i<<"  "<<posmic[i]<<" "<<posmare[i]<<"\n";
    }
    for(int i=1;i<=n;i++)
    {
        int ult = i;
        pozs[i] = i;
        for(int j=i-1;j>0;j--)
        {
            if(ult-j>d)
                break;
            if(a[j]<a[i])
            {
                pozs[i] = j;
                ult = j;
            }
        }
    }
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=0;
        int x = posmic[i];
        while(x>=pozs[i] && a[x]<a[i])
        {
            dp[i] = max(dp[i], dp[x]);
            x = posmare[x];
        }
        int prec=0;
        for(int j=posmic[i];j>=pozs[i];j--)
            if(a[j]<a[i] && a[j]>prec)
                dp[i]=max(dp[i],dp[j]), prec=a[j];
        dp[i]++;
        rez=max(rez,dp[i]);
    }
    cout<<rez;
    return 0;
}
/**

dp[i] = scorul maxim care se poate obtine daca ultimul element care creste scorul se afla pe pozitia i

dp[i] = max(dp[x]) + 1,  a[x] < a[i], distanta dintre oricare 2 pozitii consecutive cu numere < a[i] este maxim d

x = primul element din stanga lui i < a[i]

repeta atat timp a[x] < a[i]:
x = primul element din stanga lui x > a[x]

folosim binary lifting

*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35