Submission #1131927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131927		ALTAKEXE	Financial Report (JOI21_financial)	C++20	100 / 100	832 ms	80272 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
struct UNI
{
    int n;
    vector<int> par, size;
    vector<map<int, int>> mp;
    UNI(int N) : n(N), par(n + 1), size(n + 1, 1), mp(n + 1)
    {
        for (int i = 1; i <= n; i++)
            par[i] = i;
    }
    int find(int u)
    {
        if (u == par[u])
            return u;
        return par[u] = find(par[u]);
    }
    void uni(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (size[a] < size[b])
            swap(a, b);
        if (mp[a].size() < mp[b].size())
            swap(mp[a], mp[b]);
        size[a] += size[b];
        par[b] = a;
        for (auto [x, y] : mp[b])
            insert(-x, y);
    }
    void insert(int u, int v)
    {
        int p = find(u);
        auto it = mp[p].lower_bound(-u);
        if (it != mp[p].end() && it->second >= v)
            return;
        it = mp[p].insert(it, {-u, v});
        it->second = v;
        while (it != mp[p].begin() && prev(it)->second <= v)
            mp[p].erase(prev(it));
    }

    int query(int u)
    {
        int p = find(u);
        auto it = mp[p].lower_bound(-u);
        return it == mp[p].end() ? 0 : it->second;
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    vector<int> dp(n + 1, 1), a(n + 1);
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]].push_back(i);
    }
    UNI dsu(n);
    set<int> st;
    for (auto [val, vec] : mp)
    {
        for (int p : vec)
        {
            if (!st.empty() && *st.begin() < p && p - *--st.upper_bound(p) <= d)
                dsu.uni(p, *--st.upper_bound(p));
            if (!st.empty() && *st.rbegin() > p && *st.lower_bound(p) - p <= d)
                dsu.uni(p, *st.lower_bound(p));
            dp[p] = dsu.query(p) + 1;
            st.insert(p);
        }
        for (int p : vec)
            dsu.insert(p, dp[p]);
    }
    int ans = 0;
    for (int i = 0; i < dp.size(); i++)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

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