Submission #813409

#	Time	Username	Problem	Language	Result	Execution time	Memory
813409		ZHIRDILBILDIZ	Financial Report (JOI21_financial)	C++14	0 / 100	4089 ms	6328 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19) ;
int n, d, cnt, ans, dp[N + 1], p[N + 1], kol[N + 1], mn[N + 1], mx[N + 1] ;
pair<int, int> a[N + 1] ;
int get(int a)
{
    while(a != p[a])
        a = p[a] ;
    return a ;
}
void join(int a, int b)
{
    a = get(a) ;
    b = get(b) ;
    if(a == b)
        return ;
    if(kol[a] > kol[b])
        swap(a, b) ;
    mn[b] = min(mn[a], mn[b]) ;
    kol[b] += kol[a] ;
    kol[a] = 0 ;
    p[a] = b ;
}
int get_min(int a)
{
    a = get(a) ;
    return mn[a] ;
}
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)) ;
}
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.fi != p2.fi)
        return p1.fi < p2.fi ;
    else
        return p1.se > p2.se ;
}
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].fi ;
        p[i] = i ;
        mn[i] = i ;
        kol[i] = 1 ;
        a[i].se = i ;
    }
    sort(a + 1, a + n + 1, cmp) ;
    for(int i = 1 ; i <= n ; i++)
    {
        cnt++ ;
        a[i].fi = cnt ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        int l = max(1, a[i].se - d), r = a[i].se ;
        while(l < r)
        {
            int mid = (l + r) >> 1 ;
            if(get_max(1, N, mid, a[i].se, 1))
                l = mid ;
            else
                r = mid - 1 ;
        }
        if(get_max(1, N, l, a[i].se, 1))
            join(l, a[i].se) ;
        l = get_min(l) ;
        int num = get_max(1, N, l, a[i].se, 1) + 1 ;
        dp[a[i].se] = num ;
        update(1, N, a[i].se, num, 1) ;
        l = a[i].se + 1, r = min(n, a[i].se + d) ;
        while(l < r)
        {
            int mid = (l + r) >> 1 ;
            if(get_max(1, N, a[i].se + 1, mid, 1))
                r = mid ;
            else
                l = mid ;
        }
        if(r >= a[i].se + 1 && get_max(1, N, a[i].se + 1, r, 1))
            join(r, a[i].se) ;
        ans = max(ans, dp[a[i].se]) ;
    }
    cout << ans ;
    return 0 ;
}
//8 8
//4 5 1 3 6 2 7 10

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