Submission #1271589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271589		KALARRY	Financial Report (JOI21_financial)	C++20	0 / 100	4096 ms	13912 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF  = 1e9+2;

int N,D,a[300005],dp[300005],max_reach[300005],p[300005],s[300005],val[300005],prv_small[300005],nxt_small[300005];
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};
    }
    stack<pair<int,int>> ord;
    ord.push({0,0});
    for(int i = 1 ; i <= N ; i++)
    {
        while(ord.top().first > a[i])
            ord.pop();
        prv_small[i] = ord.top().second;
        if(prv_small[i]==0 || i - prv_small[i] > D)
            prv_small[i] = i;
        ord.push({a[i],i});
    }
    while(!ord.empty())
        ord.pop();
    ord.push({0,N+1});
    for(int i = N ; i >= 1 ; i--)
    {
        while(ord.top().first >= a[i])
            ord.pop();
        nxt_small[i] = ord.top().second;
        if(nxt_small[i]==N+1 || nxt_small[i] - i > D)
            nxt_small[i] = i;
    }
    sort(temp+1,temp+N+1);
    for(int j = 1 ; j <= N ; j++)
    {
        int i = temp[j].second;
        union_Sett(i,prv_small[i]);
        union_Sett(i,nxt_small[i]);
        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:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d",&N,&D);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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