Submission #661772

#	Time	Username	Problem	Language	Result	Execution time	Memory
661772		alvingogo	Financial Report (JOI21_financial)	C++14	100 / 100	644 ms	23952 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,int y){
        if(L==R){
            st[v]=max(st[v],y);
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,y);
        }
        else{
            update(2*v+2,m+1,R,p,y);
        }
        st[v]=max(st[2*v+1],st[2*v+2]);
    }
    int query(int v,int L,int R,int l,int r){
        if(l==L && r==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r);
        }
        else{
            return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
        }
    }
}st;
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.fs!=b.fs){
        return a.fs<b.fs;
    }
    return a.sc>b.sc;
}
int main(){
    AquA;
    int n;
    cin >> n;
    int d;
    cin >> d;
    vector<int> v(n);
    vector<pair<int,int> > g;
    for(int i=0;i<n;i++){
        cin >> v[i];
        g.push_back({v[i],i});
    }
    vector<int> dp(n);
    set<int> s1,s2;
    s1.insert(-1);
    sort(g.begin(),g.end(),cmp);
    st.init(n);
    int ans=0;
    for(auto h:g){
        auto y=s1.lower_bound(h.sc);
        auto z=prev(y);
        if(y!=s1.end()){
            if((*y)-h.sc-1<d && ((*y)-(*z)-1>=d)){
                s2.erase(*y);
            }
        }
        if(h.sc-(*z)-1>=d){
            s2.insert(h.sc);
        }
        s1.insert(h.sc);
        auto u=s2.upper_bound(h.sc);
        if(u==s2.begin()){
            dp[h.sc]=st.query(0,0,n-1,0,h.sc)+1;
        } 
        else{
            dp[h.sc]=st.query(0,0,n-1,*(prev(u)),h.sc)+1;
        }
        st.update(0,0,n-1,h.sc,dp[h.sc]);
        ans=max(ans,dp[h.sc]);
    }
    cout << ans << "\n";
    return 0;
}

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