提出 #66336256

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) a.begin(), a.end()
#define NUM1 998'244'353ll
#define NUM2 1'000'000'007ll
#define MOD NUM1
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sq(a_) ((a_) * (a_))
const ll INF = LLONG_MAX/7;
const ll MAX = 2'50'100ll;

template<typename T>
class segtree{
public:
    T id = -INF;
    ll n;
    vector<T> seg;

    T merge(T a, T b){
        return max(a, b);
    }

    segtree(vector<T>& a)
    {
        this->n = a.size();
        seg.resize(4*n);
        build(a, 0, 0, n - 1);
    }

    void build(vector<T>& a, ll v, ll l, ll r)
    {
        if(l == r){
            seg[v] = a[l];
            return;
        }
        ll m = (l + r)/2;
        build(a, 2*v + 1, l, m);
        build(a, 2*v + 2, m + 1, r);
        seg[v] = merge(seg[2*v + 1], seg[2*v + 2]);
    }

    void update(ll tl, ll tr, ll v, ll pos, T val)
    {
        if(tl == tr){
            seg[v] = val;
            return;
        }
        ll tm = (tl + tr)/2;
        if(pos <= tm) update(tl, tm, 2*v + 1, pos, val);
        else update(tm + 1, tr, 2*v + 2, pos, val);
        seg[v] = merge(seg[2*v + 1], seg[2*v + 2]);
    }

    T query(ll tl, ll tr, ll v, ll l, ll r)
    {
        if(l > r) return id;
        if(l == tl and r == tr) return seg[v];
        ll tm = (tl + tr)/2;
        return merge(query(tl, tm, 2*v + 1, l, min(r, tm)), query(tm + 1, tr, 2*v + 2, max(tm + 1, l), r));
    }

    void update(ll pos, T val)
    {
        update(0, n - 1, 0, pos, val);
    }

    T query(ll l, ll r){
        return query(0, n - 1, 0, l, r);    
    }
};

void solve()
{
    ll n, d, r;
    cin >> n >> d >> r;
    vector<ll> a(n);
    for(auto& x: a){
        cin >> x;
        --x;
    }
    vector<ll> pos(n);
    for(ll i = 0; i < n; i++) pos[a[i]] = i;
    vector<ll> actvals(n, 0);
    vector<ll> mvals(n, -INF);
    segtree<ll> seg(mvals);
    for(ll i = n - 1; i >= 0; i--){
        if(i + d < n){
            mvals[pos[i + d]] = actvals[pos[i + d]];
            seg.update(pos[i + d], mvals[pos[i + d]]);
        }
        ll lef = max(0ll, pos[i] - r), rig = min(n - 1, pos[i] + r);
        ll v = seg.query(lef, rig);
        if(v == -INF){
            actvals[pos[i]] = 0;
        }
        else{
            actvals[pos[i]] = 1 + v;
        }
    }
    // for(auto& x: actvals) cerr << x << ' ';
    // cerr << '\n';
    cout << *max_element(all(actvals)) << '\n';
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // fill(prods, prods + 600, mi(1));
    // fact[0] = 1;
    // for(ll i = 1; i < MAX; i++) fact[i] = i * fact[i - 1];
    // ifact[MAX - 1] = inv(fact[MAX - 1]);
    // for(ll i = MAX - 2; i >= 0; i--) ifact[i] = (i + 1) * ifact[i + 1];
    ll t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

提出情報

ジャッジ結果