Submission #1184792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184792		irmuun	Financial Report (JOI21_financial)	C++20	100 / 100	364 ms	26320 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    int n;
    vector<int>d;
    segtree(int n){
        d.resize(4*n);
    }
    int query(int v,int l,int r,int L,int R){
        if(R<L||R<l||r<L) return 0;
        if(L<=l&&r<=R) return d[v];
        int m=(l+r)>>1;
        return max(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
    }
    void update(int v,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[v]=val;
            return;
        }
        int m=(l+r)>>1;
        update(v<<1,l,m,pos,val);
        update(v<<1|1,m+1,r,pos,val);
        d[v]=max(d[v<<1],d[v<<1|1]);
    }
};

const int N=3e5+5;
int n,d;
int a[N],ord[N];
int p[N],sz[N],L[N];
set<int>active;

int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(sz[x]<sz[y]){
        swap(x,y);
    }
    p[y]=x;
    sz[x]+=sz[y];
    L[x]=min(L[x],L[y]);
}
void add(int x){
    active.insert(x);
    auto it=active.lower_bound(x);
    if(next(it)!=active.end()){
        int pos=*next(it);
        if(pos-x<=d){
            merge(x,pos);
        }
    }
    if(it!=active.begin()){
        int pos=*prev(it);
        if(x-pos<=d){
            merge(pos,x);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>d;
    iota(p+1,p+n+1,1);
    iota(L+1,L+n+1,1);
    fill(sz+1,sz+n+1,1);
    iota(ord+1,ord+n+1,1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(ord+1,ord+n+1,[&](int i,int j){
        if(a[i]!=a[j]) return a[i]<a[j];
        return i>j;
    });
    int dp[n+5],ans=0;
    segtree sg(n);
    for(int j=1;j<=n;j++){
        int i=ord[j];
        add(i);
        int left=L[find(i)];
        dp[i]=sg.query(1,1,n,left,i-1)+1;
        ans=max(ans,dp[i]);
        sg.update(1,1,n,i,dp[i]);
    }
    cout<<ans;
}

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