Submission #813507

#	Time	Username	Problem	Language	Result	Execution time	Memory
813507		ZHIRDILBILDIZ	Financial Report (JOI21_financial)	C++14	100 / 100	389 ms	26840 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, ans, dp[N + 1], p[N + 1], kol[N + 1], mn[2 * N + 1], mx[2 * 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) ;
    set<int> all ;
    for(int i = 1 ; i <= n ; i++)
    {
        auto it = all.lower_bound(a[i].se) ;
        if(it != all.end() && *it - d <= a[i].se)
        {
            join(*it, a[i].se) ;
//            cout<<"join{"<<*it<<' ' <<a[i].se<<"}\n" ;
        }
        if(it != all.begin() && *--it + d >= a[i].se)
        {
            join(*it, a[i].se) ;
//            cout<<"join{"<<*it<<' '<<a[i].se<<"}\n" ;
        }
        int num = get_max(1, N, get_min(a[i].se), a[i].se, 1) ;
        dp[a[i].se] = num + 1 ;
        update(1, N, a[i].se, num + 1, 1) ;
//        cout << get_min(a[i].se) << ' ' << a[i].se << ' ' << dp[a[i].se] << '\n' ;
        ans = max(ans, dp[a[i].se]) ;
        all.insert(a[i].se) ;
    }
    cout << ans ;
    return 0 ;
}
//13 2
//27 1 23 13 1 10 25 0 27 18 29 16 8

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