Submission #1257909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257909		ender_shayan	Financial Report (JOI21_financial)	C++20	100 / 100	287 ms	30400 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F               first
#define S               second
#define pb              push_back
#define all(x)          x.begin(),x.end()
#define Mp              make_pair
#define endl            '\n'
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define lb              lower_bound
const ll mod=1e9+7;
const int N=1e6+100;

int A[N],m,k,n,q,mn[N],mx[N],dp[N],L[N],is[N],sz[N],par[N];

vector<pii>vec;
set<int>C;
int seg[N*4];
void upd(int i,int x,int l=1,int r=n+1,int v=1){
    if(r-l==1){
        seg[v]=x;
        return;
    }
    int mid=(l+r)>>1;
    if(i<mid)upd(i,x,l,mid,v<<1);
    else upd(i,x,mid,r,v<<1|1);
    seg[v]=max(seg[v<<1],seg[v<<1|1]);
}
int get(int lx,int rx,int l=1,int r=n+1,int v=1){
    if(lx>=r || rx<=l)return 0;
    if(lx<=l && r<=rx)return seg[v];
    int mid=(l+r)>>1;
    return max(get(lx,rx,l,mid,v<<1),get(lx,rx,mid,r,v<<1|1));
}
int get_par(int v){
    if(!par[v])return v;
    return par[v]=get_par(par[v]);
}
void merg(int u,int v){
    u=get_par(u);
    v=get_par(v);
    if(u==v)return;
    if(sz[u]>sz[v])swap(u,v);
    par[u]=v;
    sz[v]+=sz[u];
    mx[v]=max(mx[v],mx[u]);
    mn[v]=min(mn[v],mn[u]);
}

int main(){
    fast_io
    cin>>n>>k;
    for1(n)cin>>A[i];
    for1(n)vec.pb({A[i],-i});
    sort(all(vec));reverse(all(vec));
    C.insert(0);
    for1(n){sz[i]=1;mx[i]=i;mn[i]=i;}
    for(pii p:vec){
        int i=-p.S;
        auto it=C.lb(i);it--;
        L[i]=(*it);
        is[i]=1;
        if(is[i-1])merg(i,i-1);
        if(is[i+1])merg(i,i+1);
        i=get_par(i);
        if(mx[i]-mn[i]+1>=k)C.insert(mx[i]);
    }
    reverse(all(vec));
    int ans=0;
    for(pii p:vec){
        int i=-p.S;
        dp[i]=get(L[i]+1,i)+1;
        upd(i,dp[i]);
        ans=max(ans,dp[i]);
   }
   cout<<ans<<endl;

}

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