Submission #818190

#	Time	Username	Problem	Language	Result	Execution time	Memory
818190		trucmai	Financial Report (JOI21_financial)	C++17	100 / 100	720 ms	61976 KiB

Main

#include <bits/stdc++.h>
using namespace std; 
#define ll long long 
const ll N = 3e5+5;
ll n,d,a[N],dp[N],mx[N];
map<ll,vector<ll>>mp;
struct segtree{
  vector<ll>tr,lz; ll n;
  segtree(){}
  void init(ll _n){ 
    n = _n; 
    tr = vector<ll>(4*n+5,0);
    lz = vector<ll>(4*n+5,-1);
  }
  void push(ll i,ll l,ll r){
    if(lz[i] == -1) return; 
    tr[i] = lz[i];
    if(l != r){
      lz[2*i] = lz[i]; 
      lz[2*i+1] = lz[i]; 
    }
    lz[i] = -1;
  }
  void upd(ll i,ll l,ll r,ll ql,ll qr,ll val){
    push(i,l,r);
    if(l > qr || r < ql) return; 
    if(ql <= l && r <= qr){
      lz[i] = val;
      push(i,l,r); 
      return; 
    }
    ll m = (r+l) >> 1;
    upd(2*i,l,m,ql,qr,val); upd(2*i+1,m+1,r,ql,qr,val); 
    tr[i] = max(tr[2*i],tr[2*i+1]);
  }
  ll get(ll i,ll l,ll r,ll ql,ll qr){
    push(i,l,r); 
    if(l > qr || r < ql) return 0;
    if(ql <= l && r <= qr) return tr[i]; 
    ll m = (r+l) >> 1; 
    ll left = get(2*i,l,m,ql,qr),right = get(2*i+1,m+1,r,ql,qr);
    return max(left,right);
  }
  void upd(ll l,ll r,ll val){ upd(1,1,n,l,r,val); }
  ll get(ll l,ll r){return get(1,1,n,l,r);}
}st;
void compress(){
  ll cnt = 0;
  for(auto node : mp){
    ++cnt;
    for(ll j : node.second) a[j] = cnt;
  } 
}
signed main(){ 
  cin>>n>>d; st.init(n);
  for(ll i = 1;i <= n;++i){
    cin>>a[i]; 
    mp[a[i]].push_back(i);
  } 
  compress(); deque<ll>dq;
  for(ll i = 1;i <= n;++i){
    while(!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); 
    while(!dq.empty() && dq.front() + d <= i) dq.pop_front(); 
    dq.push_back(i); 
    if(i >= d) mx[i] = a[dq.front()];
  }
  //for(ll i = 1;i <= n;++i) 
  //  cerr<<"DEBUG: "<<i<<" "<<mx[i]<<endl;
  for(ll i = 1;i <= n;++i){ 
    dp[i] = max(dp[i],st.get(1,a[i] - 1) + 1);
    st.upd(a[i],a[i],max(dp[i],st.get(a[i],a[i])));
    dp[i] = max(dp[i],st.get(a[i],n));
    if(i >= d) st.upd(1,mx[i] - 1,0);
    // cerr<<"DEBUG DP: "<<i<<" "<<dp[i]<<endl;
  }
  cout<<dp[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