Submission #1013905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013905		Baytoro	Financial Report (JOI21_financial)	C++17	100 / 100	1037 ms	119372 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
multiset<int> g[300005];
int t[4*300005];
void update(int id, int v, int l=0, int r=300000, int x=1) {
    if(l==r) {
        t[x]=v;
        return;
    }
    int md=(l+r)/2;
    if(id<=md) update(id,v,l,md,2*x);
    else update(id,v,md+1,r,2*x+1);
    t[x]=max(t[2*x],t[2*x+1]);
}
int mx(int lx, int rx, int l=0, int r=300000, int x=1) {
    if(l>rx || r<lx) return 0;
    if(lx<=l && r<=rx) return t[x];
    int md=(l+r)/2;
    return max(mx(lx,rx,l,md,2*x),mx(lx,rx,md+1,r,2*x+1));
}

int tr[4*300005];
void upd(int id, int v, int l=0, int r=300000, int x=1) {
    if(l==r) {
        tr[x]=v;
        return;
    }
    int md=(l+r)/2;
    if(id<=md) upd(id,v,l,md,2*x);
    else upd(id,v,md+1,r,2*x+1);
    tr[x]=min(tr[2*x],tr[2*x+1]);
}
int query(int lx, int rx, int l=0, int r=300000, int x=1) {
    if(l>rx || r<lx) return 1e9;
    if(lx<=l && r<=rx) return tr[x];

    int md=(l+r)/2;
    return min(query(lx,rx,l,md,2*x),query(lx,rx,md+1,r,2*x+1));

}

void solve() {
    int n,d;cin>>n>>d;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];

    vector<int> b=a;
    sort(all(b));
    map<int,int> mp;
    int cnt=1;
    for(int i=0;i<n;i++) {
        if(mp[b[i]]==0) mp[b[i]]=cnt++;
    }
    for(int i=0;i<n;i++) a[i]=mp[a[i]];
    vector<int> v(n);
    vector<pair<int,int>> c(n);
    for(int i=0;i<n;i++) {
        c[i]={a[i],i};
    }
    sort(all(c),[&](pair<int,int> i, pair<int,int> j) {
        if(i.fr==j.fr) return i.sc>j.sc;
        return i.fr<j.fr;
    });
    set<pair<int,int>> St;
    for(int i=0;i<n;i++) upd(i,1e9);
    for(int j=0;j<n;j++) {
        int i=c[j].sc;
        //cout<<c[j].sc<<endl;
        if(St.empty()) {
            St.insert({i,i});
            upd(i,i);
            v[i]=i;

            continue;
        }
        auto it=St.lower_bound({i,-1});
        if(it==St.end()) {
            v[i]=i;
            upd(i,i);
        }
        else if((*it).fr-i>d) {
            v[i]=i;
            upd(i,i);
        }
        else {
            upd(i,1e9);
            v[i]=query(i,n-1);
        }
        if(it!=St.begin()) {
            it--;
            if(it!=St.end()) {
                if(i-(*it).fr<=d) {
                    upd((*it).fr,1e9);
                }
            }
        }

        St.insert({i,v[i]});
    }

    /*vector<int> f(n);
    for(int i=0;i<n;i++) {
        int last=i;
        f[i]=i;
        for(int j=i+1;j<n;j++) {
            if(a[j]<=a[i] && j-last<=d) {
                last=j;
                f[i]=last;
            }
        }
    }

    for(int i=0;i<n;i++) cout<<v[i]<<' ';
    cout<<endl;
    for(int i=0;i<n;i++) cout<<f[i]<<' ';
    cout<<endl;
    cout<<endl;*/


    vector<int> dp(n,1);
    int ans=0;
    set<pair<int,int>> st;
    for(int i=0;i<n;i++) {
        while(!st.empty() && (*st.begin()).fr<i-d) {
            int id=(*st.begin()).sc;
            g[a[id]].erase(g[a[id]].find(dp[id]));
            int tmp=0;
            if(g[a[id]].size()>0) tmp=*g[a[id]].rbegin();
            update(a[id],tmp);
            st.erase(st.begin());
        }
        dp[i]=max(mx(1,a[i]-1)+1,1ll);
        ans=max(ans,dp[i]);

        st.insert({v[i],i});
        g[a[i]].insert(dp[i]);
        update(a[i],*g[a[i]].rbegin());
    }
    cout<<ans<<endl;
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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