Submission #1271591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271591		KALARRY	Financial Report (JOI21_financial)	C++20	100 / 100	190 ms	18504 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],st[1200005];
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]);
    }
}

void update(int pos,int val,int v = 1,int start = 1,int end = N)
{
    if(start==end)
    {
        st[v] = val;
        return;
    }
    int mid = (start + end)/2;
    if(pos <= mid)
        update(pos,val,2*v,start,mid);
    else
        update(pos,val,2*v+1,mid+1,end);
    st[v] = max(st[2*v],st[2*v+1]);
}

int query(int l,int r,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
        return st[v];
    int mid = (start + end)/2;
    if(r <= mid)
        return query(l,r,2*v,start,mid);
    else if(l > mid)
        return query(l,r,2*v+1,mid+1,end);
    else
        return max(query(l,mid,2*v,start,mid),query(mid+1,r,2*v+1,mid+1,end));
}

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;
        ord.push({a[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);
    }
    for(int i = 1 ; i <= N ; i++)
        temp[i] = {a[i],-i};
    sort(temp+1,temp+N+1);
    int ans = 0;
    for(int j = 1 ; j <= N ; j++)
    {
        int i = -temp[j].second;
        dp[i] = query(max_reach[i],i) + 1;
        update(i,dp[i]);
        ans = max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

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

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