| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1139478 | Nelt | Financial Report (JOI21_financial) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct node
{
ll pref = 0, suf = 0, sum = 0, mx = 0, mx1 = -1e18;
};
node merge(node a, node b)
{
node res;
res.mx = max({a.mx, b.mx, a.suf + b.pref});
res.suf = b.suf == b.sum ? b.sum + a.suf : b.suf;
res.pref = a.pref == a.sum ? a.sum + b.pref : a.pref;
res.sum = a.sum + b.sum;
res.mx1 = max(a.mx1, b.mx1);
return res;
}
struct SegTree
{
ll n;
vector<node> st;
SegTree(ll sz = 0, bool input = false)
{
n = sz;
st.resize((n + 1) << 1);
}
void modify(ll p, ll val)
{
for (st[p += n - 1] = {1, 1, 1, 1, val}; p > 1; p >>= 1)
st[p >> 1] = merge(st[p & -2], st[p | 1]);
}
node query(ll l, ll r)
{
node ansl, ansr;
for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ansl = merge(ansl, st[l++]);
if (r & 1)
ansr = merge(st[--r], ansr);
}
return merge(ansl, ansr);
}
};
void solve()
{
ll n, d;
cin >> n >> d;
ll a[n + 1];
map<ll, vector<ll>, greater<ll>> mp;
for (ll i = 1; i <= n; i++)
cin >> a[i];
for (ll i = n; i >= 1; i--)
mp[a[i]].push_back(i);
ll dp[n + 1];
for (ll i = 1; i <= n; i++)
dp[i] = 1;
SegTree st(n);
for (auto [x, v] : mp)
{
for (ll i : v)
{
ll l = i, r = n;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (st.query(i, mid).mx >= d)
r = mid - 1;
else
l = mid + 1;
}
++r;
dp[i] = max(dp[i], st.query(i, min(r, n)).mx1 + 1);
dp[i] = max(dp[i], st.query(i, n));
}
ll cur = 1;
for (ll i : v)
st.modify(i, dp[i]);
}
// for (ll i = 1; i <= n; i++)
// cout << dp[i] << " \n"[i == n];
cout << *max_element(dp + 1, dp + n + 1) << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}