| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243943 | urosk | Financial Report (JOI21_financial) | C++17 | 0 ms | 0 KiB |
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 1000000000 // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;
const ll maxn = 300005;
ll n,d;
ll a[maxn];
pll dp[maxn];
vector<ll> v;
pll t[2*maxn];
pll tmn[2*maxn];
ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
ll lazy[2*maxn];
void init(ll &v,ll tl,ll tr){
if(!v) v = ++tsz;
ll mid = (tl+tr)/2;
t[v] = tmn[v] = {-llinf,-llinf};
lazy[v] = -llinf;
if(tl==tr) return;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
pll mrg(pll a,pll b){
if(a.fi==-llinf) return b;
if(b.fi==-llinf) return a;
if(a.sc==-llinf||a.fi==-llinf) return b;
if(b.sc==-llinf||b.fi==-llinf) return a;
if(a.sc<b.sc) return a;
return b;
}
void push(ll v,ll tl,ll tr){
if(tl==tr) return;
if(lazy[v]==-llinf) return;
t[ls[v]].sc = lazy[v];
t[rs[v]].sc = lazy[v];
tmn[ls[v]].sc = lazy[v];
tmn[rs[v]].sc = lazy[v];
lazy[ls[v]] = lazy[rs[v]] = lazy[v];
lazy[v] = -llinf;
}
void upd(ll v,ll tl,ll tr,ll i,pll p){
push(v,tl,tr);
if(tl==tr){t[v] = p;tmn[v] = {i,p.sc};return;}
ll mid = (tl+tr)/2;
if(i<=mid) upd(ls[v],tl,mid,i,p);
else upd(rs[v],mid+1,tr,i,p);
t[v] = max(t[ls[v]],t[rs[v]]);
tmn[v] = mrg(tmn[ls[v]],tmn[rs[v]]);
}
pll getmx(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r||l>tr||tl>r||tl>tr) return {-llinf,-llinf};
if(tl>=l&&tr<=r) return t[v];
ll mid = (tl+tr)/2;
return max(getmx(ls[v],tl,mid,l,r),getmx(rs[v],mid+1,tr,l,r));
}
pll getmn(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r||l>tr||tl>r||tl>tr) return {-llinf,-llinf};
if(tl>=l&&tr<=r) return tmn[v];
ll mid = (tl+tr)/2;
return mrg(getmn(ls[v],tl,mid,l,r),getmn(rs[v],mid+1,tr,l,r));
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
push(v,tl,tr);
if(l>r||l>tr||tl>tr||tl>r) return;
if(tl>=l&&tr<=r){
t[v].sc = x;
tmn[v].sc = x;
lazy[v] = x;
push(v,tl,tr);
return;
}
ll mid = (tl+tr)/2;
upd(ls[v],tl,mid,l,r,x);
upd(rs[v],mid+1,tr,l,r,x);
t[v] = max(t[ls[v]],t[rs[v]]);
tmn[v] = mrg(tmn[ls[v]],tmn[rs[v]]);
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> d;
for(ll i = 1;i<=n;i++) cin >> a[i],v.pb(a[i]);
sort(all(v));
for(ll i = 1;i<=n;i++) a[i] = lower_bound(all(v),a[i])-v.begin()+1;
for(ll i = 1;i<=n;i++) dp[i] = {-llinf,-llinf};
init(root,1,n);
for(ll i = 1;i<=n;i++){
ll x = a[i];
// for(ll j = 0;j<=n;j++) cerr<<"{ "<<dp[j].fi<<", "<<dp[j].sc<<"} ";
// cerr<<endl;
while(1){
pll p = getmn(root,1,n,1,n);
// cerr<<p.fi<< " "<<p.sc<<endl;
if(p.fi==-llinf||p.sc==-llinf||p.sc>=i-d) break;
upd(root,1,n,p.fi,{-llinf,-llinf});
}
upd(root,1,n,x,n,i);
pll p = {1,i};
pll q = getmx(root,1,n,1,x-1);
p = max(p,{q.fi+1,i});
p = max(p,getmx(root,1,n,x,x));
upd(root,1,n,x,p);
}
while(1){
pll p = getmn(root,1,n,1,n);
// cerr<<p.fi<< " "<<p.sc<<endl;
if(p.fi==-llinf||p.sc==-llinf||p.sc>=i-d) break;
upd(root,1,n,p.fi,{-llinf,-llinf});
}
pll ans = getmx(root,1,n,1,n);
cout<<ans.fi<<endl;
}