Submission #812060

#	Time	Username	Problem	Language	Result	Execution time	Memory
812060		vjudge1	Financial Report (JOI21_financial)	C++14	65 / 100	2069 ms	36288 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19), NS = 7000 ;
int n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<int> s ;
map<int, int> mp ;
void update(int l, int r, int ind, int num, int v)
{
    if(l > ind || r < ind)
        return ;
    if(l == r)
    {
        mx[v] = num ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update(l, mid, ind, num, v * 2) ;
    update(mid + 1, r, ind, num, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
int get_max(int l, int r,int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return 0 ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    return max(get_max(l, mid, l1, r1, v * 2), get_max(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> d ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        s.insert(a[i]) ;
    }
    for(int i : s)
    {
        cnt++ ;
        mp[i] = cnt ;
    }
    for(int i = 1 ; i <= n ; i++)
        a[i] = mp[a[i]] ;
    if(n <= 400)
    {
        int ans = 0 ;
        for(int i = n ; i >= 1 ; i--)
        {
            int mx = 0 ;
            for(int j = i + 1 ; j <= n ; j++)
                if(a[j] > a[i])
                {
                    bool flag = 0 ;
                    vector<int> v ;
                    v.push_back(i) ;
                    for(int q = i + 1 ; q <= j ; q++)
                        if(a[q] < a[j])
                        {
                            if(q - v.back() > d)
                                flag = 1 ;
                            v.push_back(q) ;
                        }
                    if(j - v.back() > d)
                        flag = 1 ;
                    if(!flag)
                        mx = max(mx, dp[j]) ;
                }
            dp[i] = mx + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(n <= 7000)
    {
        int ans = 0 ;
        for(int i = n ; i >= 1 ; i--)
        {
            int ls = i ;
            dp[i] = max(dp[i], 1) ;
            for(int j = i - 1 ; j >= 1 ; j--)
            {
                if(ls - j > d)
                    break ;
                if(a[j] < a[i])
                {
                    ls = j ;
                    dp[j] = max(dp[j], dp[i] + 1) ;
                }
            }
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == 1)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
            update(1, N, i, a[i], 1) ;
        for(int i = n ; i >= 1 ; i--)
        {
            int l = i, r = n + 1 ;
            while(l + 1 < r)
            {
                int mid = (l + r) >> 1 ;
                if(get_max(1, N, i, mid, 1) > a[i])
                    r = mid ;
                else
                    l = mid ;
            }
            dp[i] = dp[r] + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == n)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            int num = get_max(1, N, 1, a[i] - 1, 1) ;
            ans = max(ans, num + 1) ;
            update(1, N, a[i], num + 1, 1) ;
        }
        cout << ans ;
        return 0 ;
    }
    return 0 ;
}

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