Submission #1271588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271588		KALARRY	Financial Report (JOI21_financial)	C++20	48 / 100	4094 ms	9096 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF  = 1e9;

int N,D,a[300005],dp[300005],max_reach[300005],p[300005],s[300005],val[300005],prv_small[300005],nxt_small[300005];
map<int,int> prv_emf;
pair<int,int> temp[300005];

int find_Sett(int i)
{
    if(p[i]==i)
        return i;
    p[i] = find_Sett(p[i]);
    return p[i];
}

bool is_Same_Sett(int i,int j)
{
    return find_Sett(i)==find_Sett(j);
}

int get_val(int i)
{
    return val[find_Sett(i)];
}

void union_Sett(int i,int j)
{
    if(is_Same_Sett(i,j))
        return ;
    int x = find_Sett(i);
    int y = find_Sett(j);
    if(s[x] >= s[y])
    {
        p[y] = x;
        s[x] += s[y];
        val[x] = min(val[x],val[y]);
    }
    else
    {
        p[x] = y;
        s[y] += s[x];
        val[y] = min(val[y],val[x]);
    }
}

int main()
{
    scanf("%d%d",&N,&D);
    for(int i = 1 ; i <= N ; i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
        p[i] = i;
        s[i] = 1;
        val[i] = i;
        temp[i] = {a[i],i};
    }
    sort(temp+1,temp+N+1);
    for(int j = 1 ; j <= N ; j++)
    {
        int i = temp[j].second;
        for(int x = i-1 ; x >= max(i-D,1) ; x--)
            if(a[x] <= a[i])
                union_Sett(i,x);
        for(int x = i+1 ; x <= min(N,i+D) ; x++)
            if(a[x] < a[i])
                union_Sett(i,x);
        max_reach[i] = get_val(i);
    }
    a[0] = 0;
    int ans = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = 1;
        for(int l = max_reach[i] ; l < i ; l++)
            if(a[l] < a[i])
                dp[i] = max(dp[i],dp[l] + 1);
        ans = max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d",&N,&D);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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