Submission #1192360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192360		meisgood	Financial Report (JOI21_financial)	C++20	100 / 100	1424 ms	96892 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int gp[300003] ;
int dsu(int x){
  if (x==gp[x]) return x ;
  gp[x]=dsu(gp[x]) ;
  return gp[x] ;
}
int ml[300003] ;
struct segt {
  int seg[1200003] ;
  void build(int id,int l,int r){
    if (l==r) seg[id]=0 ;
    else {
      int md=(l+r)/2 ;
      build(id*2,l,md),build(id*2+1,md+1,r) ;
    }
  }
  void upd(int id,int l,int r,int x,int v){
    if (l==r&&l==x) seg[id]=v ;
    else if (l>x||r<x) return ;
    else {
      int md=(l+r)/2 ;
      upd(id*2,l,md,x,v),upd(id*2+1,md+1,r,x,v) ;
      seg[id]=max(seg[id*2],seg[id*2+1]) ;
    }
  }
  int query(int id,int l,int r,int ql,int qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return 0 ;
    else {
      int md=(l+r)/2 ;
      return max(query(id*2,l,md,ql,qr),query(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} ;
signed main(){
  int n,d,i,j ;
  cin >> n >> d ;
  for (i = 1 ; i <= n ; i ++) gp[i]=i ;
  int arr[300003] ;
  set <int> st ;
  for (i = 1 ; i <= n ; i ++) cin >> arr[i],st.insert(arr[i]) ;
  i=1 ;
  map <int,int> mp ;
  for (auto x : st){
    mp[x]=i ;
    i++ ;
  }
  for (i = 1 ; i <= n ; i ++) arr[i]=mp[arr[i]] ;
  set <int> stt ;
  map <int,vector<int>> vvv ;
  segt seg ;
  seg.build(1,1,n) ;
  for (i = 1 ; i <= n ; i ++) vvv[arr[i]].push_back(i) ;
  for (auto [a,v] : vvv){
    for (auto x : v){
      stt.insert(x) ;
      auto it=stt.find(x) ;
      if (it!=stt.begin()){
        auto it2=it ; it2-- ;
        if (abs(*it2-*it)<=d) gp[dsu(*it)]=dsu(*it2) ;
      }
      if (it!=--stt.end()){
        auto it2=it ; it2++ ;
        if (abs(*it2-*it)<=d) gp[dsu(*it2)]=dsu(*it) ;
      }
    }
    for (auto x : v) ml[x]=dsu(x) ;
    // for (i = 1 ; i <= n ; i ++) cout << dsu(i) << " " ; cout << endl ;
  }
  // for (i = 1 ; i <= n ; i ++) cout << ml[i] << " " ; cout << endl ;
  for (auto [a,v] : vvv){
    reverse(v.begin(),v.end()) ;
    for (auto x : v){
      seg.upd(1,1,n,x,seg.query(1,1,n,ml[x],x)+1) ;
    }
  }
  cout << seg.query(1,1,n,1,n) << endl ;
  return 0 ;
}

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