Submission #771047

#	Time	Username	Problem	Language	Result	Execution time	Memory
771047		SamAnd	Financial Report (JOI21_financial)	C++17	100 / 100	428 ms	28580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 300005;

int n, d;
int a[N];

int p[N];
int l[N], r[N];
int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

void kpc(int x, int y)
{
    if (abs(x - y) > d)
        return;
    x = fi(x);
    y = fi(y);
    p[x] = y;
    l[y] = min(l[y], l[x]);
    r[y] = max(r[y], r[x]);
}

int maxu[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        maxu[pos] = max(maxu[pos], y);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    maxu[pos] = max(maxu[pos * 2], maxu[pos * 2 + 1]);
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return maxu[pos];
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

void solv()
{
    cin >> n >> d;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<pair<int, int> > v;
    for (int i = 1; i <= n; ++i)
        v.push_back(m_p(a[i], -i));
    sort(all(v));

    for (int i = 1; i <= n; ++i)
    {
        l[i] = r[i] = i;
        p[i] = i;
    }

    set<int> s;
    for (int i = 0; i < n; ++i)
    {
        v[i].se *= -1;
        s.insert(v[i].se);
        auto it = s.find(v[i].se);
        if (it != s.begin())
        {
            --it;
            kpc(v[i].se, *it);
            ++it;
        }
        if (it != (--s.end()))
        {
            ++it;
            kpc(v[i].se, *it);
            --it;
        }
        int u = l[fi(v[i].se)];

        int dp = qry(1, n, u, v[i].se, 1) + 1;
        ubd(1, n, v[i].se, dp, 1);
    }

    cout << maxu[1] << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    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