Submission #705020

#	Time	Username	Problem	Language	Result	Execution time	Memory
705020		MtSaka	Financial Report (JOI21_financial)	C++17	100 / 100	639 ms	77320 KiB

Main

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
struct dsu{
  private:
  vector<int>p;
  vector<int>mx;
  public:
  dsu(int n):p(n,-1),mx(n,0){iota(all(mx),0);}
  int root(int a){return p[a]<0?a:p[a]=root(p[a]);}
  int same(int a,int b){return root(a)==root(b);}
  int get(int a){return mx[root(a)];}
  void merge(int a,int b){
    a=root(a),b=root(b);
    if(a==b)return;
    if(p[a]>p[b])swap(a,b);
    p[a]+=p[b];
    p[b]=a;
    chmax(mx[a],mx[b]);
  }
};
struct segtree{
  private:
  int n,sz,idx;
  vector<int>seg;
  void update(int i){seg[i]=max(seg[i<<1],seg[i<<1|1]);}
  public:
  segtree(int n):n(n){
    sz=1,idx=0;
    while(sz<n)sz<<=1,idx++;
    seg.resize(sz<<1);
  }
  void set(int i,int a){
    i+=sz;
    seg[i]=a;
    i>>=1;
    while(i>0){
      update(i);i>>=1;
    }
  }
  int prod(int l,int r){
    l+=sz,r+=sz;
    int ret=0;
    while(l<r){
      if(l&1)chmax(ret,seg[l++]);
      if(r&1)chmax(ret,seg[--r]);
      l>>=1,r>>=1;
    }
    return ret;
  }
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,d;
  cin>>n>>d;
  vector<int>a(n);
  for(auto&e:a)cin>>e;
  auto b=a;
  sort(all(b));
  b.erase(unique(all(b)),b.end());
  for(auto&e:a)e=lower_bound(all(b),e)-b.begin();
  vector<vector<int>>idx(b.size());
  rep(i,0,n)idx[a[i]].emplace_back(i);
  dsu uf(n);
  set<int>vis;
  vis.emplace(-1e9);
  vis.emplace(1e9);
  
  vector<vector<int>>to_delete(n+1);
  for(auto&v:idx){
    reverse(all(v));
    for(auto i:v){
      auto it=vis.lower_bound(i);
      int nxt=*it;
      int pre=*prev(it);
      if(i-pre<=d)uf.merge(i,pre);
      if(nxt-i<=d)uf.merge(i,nxt);
      vis.emplace(i);
      to_delete[min(n,uf.get(i)+d)].emplace_back(i);
    }
  }
  vector<int>dp(n,0);
  vector<multiset<int>>v(n);
  segtree seg(n);
  int ans=0;
  rep(i,0,n){
    dp[i]=seg.prod(0,a[i])+1;
    chmax(ans,dp[i]);
    v[a[i]].insert(dp[i]);
    seg.set(a[i],*v[a[i]].rbegin());
    for(auto j:to_delete[i]){
      v[a[j]].erase(v[a[j]].find(dp[j]));
      seg.set(a[j],v[a[j]].empty()?0:*v[a[j]].rbegin());
    }
  }
  cout<<ans<<endl;
}

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