Submission #1268364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268364		k12_khoi	Financial Report (JOI21_financial)	C++17	100 / 100	1237 ms	159348 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=3e5+5;
const int oo=1e9+1;

int n,D,res;
int a[N];

namespace sub1
{
    void ql(int i,int ma,int cur)
    {
        if (i==n)
        {
            res=max(res,cur);
            return;
        }

        for (int j=i+1;j<=i+D;j++)
        {
            if (j>n) break;

            ql(j,max(ma,a[j]),cur+(ma<a[j]));
        }
    }

    void solve()
    {
        res=0;
        for (int i=1;i<=n;i++)
        ql(i,a[i],1);

        cout << res;
    }
}

namespace sub2
{
    const int K=2005;

    int h,limit;
    int dp[K][K];
    vector <int> ve;


    void solve()
    {
        ve.clear();
        for (int i=1;i<=n;i++)
        ve.push_back(a[i]);

        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        h=ve.size();

        for (int i=1;i<=n;i++)
        a[i]=lower_bound(ve.begin(),ve.end(),a[i])-ve.begin()+1;


        for (int i=1;i<=n;i++)
        for (int j=1;j<=h;j++)
        dp[i][j]=-oo;

        for (int i=1;i<=n;i++)
        dp[i][a[i]]=1;

        res=0;
        for (int i=1;i<=n;i++)
        for (int k=1;k<=h;k++)
        if (dp[i][k]!=-oo)
        {
            res=max(res,dp[i][k]);

            limit=min(i+D,n);
            for (int j=i+1;j<=limit;j++)
            dp[j][max(k,a[j])]=max(dp[j][max(k,a[j])],dp[i][k]+(k<a[j]));
        }

        cout << res;
    }
}

namespace sub6
{
    int mx_bit;
    int save[N],last[N];
    multiset <int> bit[N];
    priority_queue <pii,vector<pii>,greater<pii>> q;
    vector <int> ve;

    void fenwick_add(int u,int v)
    {
        for (int idx=u;idx<=mx_bit;idx+=idx&-idx)
        bit[idx].insert(save[v]);
    }

    void fenwickDel(int u,int v)
    {
        for (int idx=u;idx<=mx_bit;idx+=idx&-idx)
        bit[idx].erase(bit[idx].find(save[v]));
    }

    int fenwick___get(int u)
    {
        int ans=0;

        for (int idx=u;idx>0;idx-=idx&-idx)
        if (!bit[idx].empty()) ans=max(ans,*--bit[idx].end());

        return ans;
    }

    void solve()
    {
        ve.clear();
        for (int i=1;i<=n;i++)
        ve.push_back(a[i]);

        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        mx_bit=ve.size();

        for (int i=1;i<=n;i++)
        a[i]=lower_bound(ve.begin(),ve.end(),a[i])-ve.begin()+1;


        while (!q.empty()) q.pop();

        res=0;
        for (int i=1;i<=n;i++)
        {
            save[i]=fenwick___get(a[i]-1)+1;
            fenwick_add(a[i],i);

            res=max(res,save[i]);

            while (!q.empty() and q.top().X<a[i] and last[q.top().X]<=i-D)
            {
                fenwickDel(q.top().X,q.top().Y);
                q.pop();
            }


            last[a[i]]=i;

            q.push(make_pair(a[i],i));
        }

        cout << res;
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> D;
    for (int i=1;i<=n;i++)
    cin >> a[i];

    sub6::solve();
}

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