Submission #1243939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243939		urosk	Financial Report (JOI21_financial)	C++17	53 / 100	4094 ms	42696 KiB

Main

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 100000000000000000LL // 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 = long long;
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.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);
        if(p.sc==-llinf||p.sc>=n-d) break;
        upd(root,1,n,p.fi,{-llinf,-llinf});
    }
    pll ans = getmx(root,1,n,1,n);
    cout<<ans.fi<<endl;
}

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