Submission #661717

#	Time	Username	Problem	Language	Result	Execution time	Memory
661717		victor_gao	Financial Report (JOI21_financial)	C++17	100 / 100	529 ms	20480 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,O3")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
vector<int>no;
struct not_bigest_segtree{
    int mn[4*N],tag[4*N];
    bool surv[4*N];
    void push(int i){
        if (tag[i]){
            if (surv[2*i]){
                tag[2*i]=tag[i];
                mn[2*i]=tag[i];
            }
            if (surv[2*i+1]){
                tag[2*i+1]=tag[i];
                mn[2*i+1]=tag[i];
            }
            tag[i]=0;
        }
    }
    void dfs(int l,int r,int i,int p,int d){
        if (!surv[i]||mn[i]>=p-d) return;
        if (l==r){
            no.push_back(l);
            surv[i]=0; mn[i]=1e9; tag[i]=0;
            return;
        }
        int mid=(l+r)>>1;
        push(i);
        if (mn[2*i]<p-d&&surv[2*i]) dfs(l,mid,2*i,p,d);
        if (mn[2*i+1]<p-d&&surv[2*i+1]) dfs(mid+1,r,2*i+1,p,d);
        mn[i]=min(mn[2*i],mn[2*i+1]);
        surv[i]=(surv[2*i]|surv[2*i+1]);
        if (!surv[i]){
            tag[i]=0;
            mn[i]=1e9;
        } 
    }
    void add(int l,int r,int i,int p){
        if (l==r){
            surv[i]=1;
            return;
        }
        int mid=(l+r)>>1;
        push(i);
        if (p<=mid) add(l,mid,2*i,p);
        else add(mid+1,r,2*i+1,p);
        surv[i]=(surv[2*i]|surv[2*i+1]);
    }
    void modify(int l,int r,int i,int ll,int rr,int val){
        if (ll>rr) return;
        if (!surv[i]) return;
        if (ll<=l&&rr>=r){
            if (surv[i]){
                tag[i]=val; mn[i]=val;
            }
            return;
        }
        int mid=(l+r)>>1;
        push(i);
        if (rr<=mid) modify(l,mid,2*i,ll,rr,val);
        else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val);
        else {
            modify(l,mid,2*i,ll,rr,val);
            modify(mid+1,r,2*i+1,ll,rr,val);
        }
        mn[i]=min(mn[2*i],mn[2*i+1]);
    }
}surv;
struct is_bigest_segtree{
    int mx[4*N];
    void modify(int l,int r,int i,int p,int val,bool flag){
        if (l==r){
            if (flag) mx[i]=val;
            else mx[i]=max(val,mx[i]);
            return;
        }
        int mid=(l+r)>>1;
        if (p<=mid) modify(l,mid,2*i,p,val,flag);
        else modify(mid+1,r,2*i+1,p,val,flag);
        mx[i]=max(mx[2*i],mx[2*i+1]);
    }
    int query(int l,int r,int i,int ll,int rr){
        if (ll>rr) return 0;
        if (ll<=l&&rr>=r) return mx[i];
        int mid=(l+r)>>1;
        if (rr<=mid) return query(l,mid,2*i,ll,rr);
        else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
        else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
    }
}seg;
int dp[N],n,d,a[N];
signed main(){
    fast
   // freopen("in.txt","r",stdin);
    cin>>n>>d;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        uni.in(a[i]);
    }
    uni.build();
    for (int i=1;i<=n;i++)
        a[i]=uni.idx(a[i]);
    for (int i=1;i<=4*n+5;i++)
        surv.mn[i]=1e9;
    int cnt=0;
    for (int i=1;i<=n;i++){
        surv.dfs(1,n,1,i,d);
        for (auto j:no){
            cnt++;
            seg.modify(1,n,1,j,0,1);
        }
        assert(cnt<=n);
        no.clear();
        dp[i]=seg.query(1,n,1,1,a[i]-1)+1;
        surv.add(1,n,1,a[i]);
        surv.modify(1,n,1,a[i],n,i);
        seg.modify(1,n,1,a[i],dp[i],0);
    }
    int ans=1;
    for (int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    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: 35 / 35