Submission #670308

#	Time	Username	Problem	Language	Result	Execution time	Memory
670308		bachhoangxuan	Financial Report (JOI21_financial)	C++17	65 / 100	4046 ms	42612 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define pii pair<int,int>
int n,d,a[maxn],Min[maxn],r[maxn],dp[maxn];
vector<int> p,pos[maxn];
namespace ST{
    int tree[4*maxn];
    void build(int l,int r,int id){
        if(l==r){
            tree[id]=-1;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        tree[id]=max(tree[id<<1],tree[id<<1|1]);
    }
    int query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl) return -1;
        if(tl<=l && r<=tr) return tree[id];
        int mid=(l+r)>>1;
        return max(query(l,mid,id<<1,tl,tr),query(mid+1,r,id<<1|1,tl,tr));
    }
    int query2(int l,int r,int id,int val){
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(tree[id<<1]>val) return query2(l,mid,id<<1,val);
        else return query2(mid+1,r,id<<1|1,val);
    }
    int query1(int l,int r,int id,int p,int val){
        if(l==r){
            if(tree[id]>val) return l;
            else return n+1;
        }
        int mid=(l+r)>>1;
        if(p<=mid){
            int pos=query1(l,mid,id<<1,p,val);
            if(pos!=n+1) return pos;
            if(tree[id<<1|1]>val) return query2(mid+1,r,id<<1|1,val);
            else return n+1;
        }
        else return query1(mid+1,r,id<<1|1,p,val);
    }
    void update(int l,int r,int id,int p,int val){
        if(l==r){
            tree[id]=val;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) update(l,mid,id<<1,p,val);
        else update(mid+1,r,id<<1|1,p,val);
        tree[id]=max(tree[id<<1],tree[id<<1|1]);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> d;
    //Compress numbers
    for(int i=1;i<=n;i++){
        cin >> a[i];
        p.push_back(a[i]);
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(p.begin(),p.end(),a[i])-p.begin()+1;
    //calculate Min[i] is the minimum number from i->i+d-1
    multiset<int> s;
    for(int i=n;i>=n-d+1;i--){s.insert(a[i]);r[i]=n;}
    for(int i=n-d+1;i>=1;i--){
        Min[i]=*s.begin();
        s.erase(lower_bound(s.begin(),s.end(),a[i+d-1]));
        s.insert(a[i-1]);
    }
    // calculate r[i] is the farthest that i can go to
    ST::build(1,n-d+1,1);
    ST::update(1,n-d+1,1,n-d+1,Min[n-d+1]);
    for(int i=n-d;i>=1;i--){
        ST::update(1,n-d+1,1,i,Min[i]);
        r[i]=min(n,ST::query1(1,n-d+1,1,i,a[i])+d-1);
    }
    //calculate dp with sort a[i]
    for(int i=1;i<=n;i++) pos[a[i]].push_back(i);
    int ans=0;
    ST::build(1,n,1);
    ST::update(1,n,1,n,0);
    for(int i=n;i>=1;i--){
        for(int x:pos[i]){
            dp[x]=ST::query(1,n,1,x,r[x])+1;
            ans=max(ans,dp[x]);
        }
        for(int x:pos[i]) ST::update(1,n,1,x,dp[x]);
    }
    cout << ans << '\n';
}

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