Submission #1244082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244082		m5588ohammed	Financial Report (JOI21_financial)	C++20	17 / 100	2389 ms	74492 KiB

Main

#include <bits/stdc++.h>
#define endl "\n"
#define mod 1000000007
using namespace std;
struct node{
    int suf,pre,ans,siz=1;
};
const int N=(1<<20);
int MX[N*2+5];
node Tree[N*2+5];
node merge(node A,node B){
    node C;
    C.pre=A.pre;
    if(A.pre==A.siz) C.pre+=B.pre;
    C.suf=B.pre;
    if(B.suf==B.siz) C.suf+=A.suf;
    C.ans=max({A.ans,B.ans,C.pre,C.suf});
    C.siz=A.siz+B.siz;
    return C;
}
void update(int i){
    i+=N;
    Tree[i].suf=Tree[i].pre=Tree[i].siz=Tree[i].ans=1;
    i/=2;
    while(i!=0){
        Tree[i]=merge(Tree[i*2],Tree[i*2+1]);
        i/=2;
    }
    return;
}
node solve(int l1,int r1,int i,int l,int r){
    if(l1>r||l>r1) return {0,0,0,1};
    if(l<=l1&&r1<=r) return Tree[i];
    return merge(solve(l1,(l1+r1)/2,i*2,l,r),solve((l1+r1)/2+1,r1,i*2+1,l,r));
}
int n,d,arr[300010],pt[300010];
int dp[300010];
void update2(int i){
    i+=N;
    MX[i]=dp[i-N];
    i/=2;
    while(i!=0){
        MX[i]=max(MX[i*2],MX[i*2+1]);
        i/=2;
    }
    return;
}
int solve2(int l1,int r1,int i,int l,int r){
    if(l1>r||l>r1) return 0;
    if(l<=l1&&r1<=r) return MX[i];
    return max(solve2(l1,(l1+r1)/2,i*2,l,r),solve2((l1+r1)/2+1,r1,i*2+1,l,r));
}
void compress(){
    set <int> comp;
    map <int,int> key;
    for(int i=1;i<=n;i++){
        comp.insert(arr[i]);
    }
    int cnt=0;
    for(int i:comp){
        key[i]=++cnt;
    }
    for(int i=1;i<=n;i++) arr[i]=key[arr[i]];
    return;
}
void check(int i){
    int l=1,r=i;
    while(l<=r){
        int mid=(l+r)/2;
        if(solve(0,N-1,1,mid,i).ans+1<=d){
            pt[i]=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>d;
    for(int i=1;i<=n;i++) cin>>arr[i];
    compress();
    vector <int> v[300001];
    for(int i=1;i<=n;i++){
        v[arr[i]].push_back(i);
    }
    for(int val=n;val>=1;val--){
        for(int i:v[val]) check(i);
        for(int i:v[val]) update(i);
    }
    int mx=0;
    for(int val=1;val<=n;val++){
        for(int i:v[val]){
            dp[i]=solve2(0,N-1,1,pt[i],i)+1;
            mx=max(mx,dp[i]);
        }
        for(int i:v[val]) update2(i);
    }
    cout<<mx<<endl;
}

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