Submission #1139481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139481		Nelt	Financial Report (JOI21_financial)	C++20	100 / 100	1613 ms	66188 KiB

Main

#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, len = 0, mx1 = -1e18;
};
node merge(node a, node b)
{
    node res;
    res.mx = max({a.mx, b.mx, a.suf + b.pref});
    res.len = a.len + b.len;
    res.suf = b.suf == b.len ? b.len + a.suf : b.suf;
    res.pref = a.pref == a.len ? a.len + 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, {0, 0, 0, 0, 1, (ll)-1e18});
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--) st[i] = merge(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, ll val)
    {
        for (st[p += n - 1] = {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);
    st.build();
    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);
        }
        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";
}

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