Submission #1216789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216789		Younis_Dwai	Financial Report (JOI21_financial)	C++20	19 / 100	2709 ms	88496 KiB

Main

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
#define popp pop_back
#define in insert
#define endl "\n"
#define mid (l+r)/2
using namespace std;
const int N=3e5+5;
struct item{
       int mx=0,mxp=0,mxs=0,sz;
};
int n,D,b[N],tree[N*4],dp[N],tt=0;
vector<int> adj[N];
item T[N*4];
item combine(item x , item y){
     item ret;
     ret.mxp=x.mxp;ret.mxs=y.mxs;
     if(x.mxp==x.sz) ret.mxp=x.mxp+y.mxp;
     if(y.mxs==y.sz) ret.mxs=y.mxs+x.mxs;
     ret.mx=max({x.mx,y.mx,x.mxs+y.mxp});
     ret.sz=x.sz+y.sz;
     return ret;
}
void build(int node , int l , int r){
     T[node]={r-l+1,r-l+1,r-l+1,r-l+1};
     if(l==r) return ;
     build(node*2,l,mid);
     build(node*2+1,mid+1,r);
     return ;
}
void flip(int node , int l , int r , int id){
     if(l==r){
        T[node]={0,0,0,1};
        return ;
     }
     else if(id<=mid) flip(node*2,l,mid,id);
     else flip(node*2+1,mid+1,r,id);
     T[node]=combine(T[node*2],T[node*2+1]);
     return ;
}
item longest(int node , int l  ,int r , int s , int e){
    if(l>=s && r<=e) return T[node];
    else if(l>e || r<s) return {0,0,0,1};
    return combine(longest(node*2,l,mid,s,e),longest(node*2+1,mid+1,r,s,e));
}
int query(int node , int l , int r ,int s  , int e){
    if(l>=s && r<=e) return tree[node];
    else if(l>e || r<s) return 0;
    return max(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
}
void upd(int node , int l ,  int r , int id , int v){
     if(l==r){
        tree[node]=v;
        return ;
     }
     else if(id<=mid) upd(node*2,l,mid,id,v);
     else upd(node*2+1,mid+1,r,id,v);
     tree[node]=max(tree[node*2],tree[node*2+1]);
     return ;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>D;
    build(1,1,n);
    vector<int> v;map<int,int> mp;
    for(int i=1;i<=n;i++) cin>>b[i],v.pb(b[i]);
    sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
    for(auto u : v) mp[u]=++tt;
    for(int i=1;i<=n;i++){
            b[i]=mp[b[i]];
            adj[b[i]].pb(i);
            //cout<<b[i]<<' ';
    }

    int ret=1;
    for(int i=1;i<=tt;i++){
        for(auto u : adj[i]){
            dp[u]=1;
            int l=1,r=u,midd=(l+r)/2;
            while(l<r){
                  item x=longest(1,1,n,midd,u);
                  if(x.mx<=D) r=midd;
                  else l=midd+1;
                  midd=(l+r)/2;
            }
            dp[u]=1+query(1,1,n,midd,u);
            ret=max(ret,dp[u]);
            //cout<<" # "<<u<<' '<<' '<<midd<<' '<<dp[u]<<endl;
        }
        for(auto u : adj[i]){
            upd(1,1,n,u,dp[u]);
            flip(1,1,n,u);
        }
    }
    cout<<ret;
    return 0;
}

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