Submission #1243944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243944		Almonther	Financial Report (JOI21_financial)	C++20	33 / 100	1939 ms	563428 KiB

Main

#include<bits/stdc++.h>

#define ll long long
#define co cout<<

using namespace std;
// stuff
const int maxn=4e5+5,N=524288*2;
ll n,d;
multiset<ll>tre[N*4+5];
ll mntre[N*4+5],mnlazy[N*4+5];
ll spa[maxn][20],endd[maxn];
ll maxof(ll l,ll r,ll i,ll lq,ll rq){
    if(l>rq||r<lq) return 0;
    if(lq<=l&&r<=rq) return *tre[i].rbegin();
    ll mid=(l+r)/2;
    return max(maxof(l,mid,i*2,lq,rq),maxof(mid+1,r,i*2+1,lq,rq));
}
void add(ll x,ll val){
    x+=N;
    tre[x].insert(val);
    x/=2;
    while(x){
        tre[x].clear();
        ll x1=0,y=0;
        if(tre[x*2].size()) x1=*tre[x*2].rbegin();
        if(tre[x*2+1].size()) y=*tre[x*2+1].rbegin();
        tre[x].insert(max(x1,y));
        x/=2;
    }
}
void rem(ll x,ll val){
    x+=N;
    tre[x].extract(val);
    x/=2;
    while(x){
        tre[x].clear();
        ll x1=0,y=0;
        if(tre[x*2].size()) x1=*tre[x*2].rbegin();
        if(tre[x*2+1].size()) y=*tre[x*2+1].rbegin();
        tre[x].insert(max(x1,y));
        x/=2;
    }
}
void pushmn(ll x){
    if(x<N) mnlazy[x*2]=min(mnlazy[x*2],mnlazy[x]),mnlazy[x*2+1]=min(mnlazy[x*2+1],mnlazy[x]);
    mntre[x]=min(mnlazy[x],mntre[x]);
    mnlazy[x]=n;
}
ll minof(ll l,ll r,ll i,ll lq,ll rq){
    pushmn(i);
    if(l>rq||r<lq) return n;
    if(lq<=l&&r<=rq) return mntre[i];
    ll mid=(l+r)/2;
    return min(minof(l,mid,i*2,lq,rq),minof(mid+1,r,i*2+1,lq,rq));
}
void minupd(ll l,ll r,ll i,ll lq,ll rq,ll x){
    pushmn(i);
    if(l>rq||r<lq) return;
    if(lq<=l&&r<=rq){
        mnlazy[i]=x;
        pushmn(i);
        return;
    }
    ll mid=(l+r)/2;
    minupd(l,mid,i*2,lq,rq,x);
    minupd(mid+1,r,i*2+1,lq,rq,x);
    mntre[i]=min(mntre[i*2],mntre[i*2+1]);
}
ll mn(ll l,ll r){
    if(r==l) return spa[r][0];
    ll x=__lg(r-l);
    return min(spa[l][x],spa[r-(1<<x)+1][x]);
}
void solve(){
    cin>>n>>d;
    for(int i=0;i<N*4;i++){
        mntre[i]=n+1,mnlazy[i]=n+1;
        tre[i].insert(0);
    }
    ll arr[n+5],cnt=0;
    map<ll,ll>comp;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        comp[arr[i]];
    }
    for(auto &i:comp) i.second=cnt++;
    for(int i=n-1;i>=0;i--){
        arr[i]=comp[arr[i]];
        endd[i]=minof(0,N-1,1,arr[i]+1,n);
        for(int j=0;!j||i+(1<<(j-1))<n;j++){
            if(j==0) spa[i][j]=arr[i];
            else spa[i][j]=min(spa[i][j-1],spa[i+(1<<(j-1))][j-1]);
        }
        minupd(0,N-1,1,0,mn(i,min(i+d-1,n-1)),min(i+d,n));
    }
    set<array<ll,3>>s;
    for(int i=0;i<n;i++){
        while(s.size()&&(*s.begin())[0]==i){
            rem((*s.begin())[1],(*s.begin())[2]);
            s.erase(s.begin());
        }
        ll ans=maxof(0,N-1,1,0,arr[i]-1)+1;
        add(arr[i],ans);
        if(i==n-1) co maxof(0,N-1,1,0,n);
        s.insert({endd[i],arr[i],ans});
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

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