Submission #1164973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164973		veliak	Financial Report (JOI21_financial)	C++20	0 / 100	152 ms	26272 KiB

Main

// #define _GLIBCXX_DEBUG
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;

template<class T> using ordered_set = __gnu_pbds::tree<T,
    __gnu_pbds::null_type,
    less<T>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define all(v) v.begin(), v.end()

#ifdef LOCAL
#define debug(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
#else
#define debug(x)
#endif

#ifdef LOCAL
#define debug_vec(x)                           \
    cout << __LINE__ << ": " << (#x) << " = "; \
    for (auto &y : x)                          \
        cout << y << " ";                      \
    cout << endl;
#else
#define debug_vec(x)
#endif


using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

auto now_rand = chrono::high_resolution_clock::now();
mt19937 rnd(now_rand.time_since_epoch().count());

const ll mod = 1e9 + 7;

struct dsu {
    vector<int> p, s, left;
    inline void init(int n) {
        p.resize(n);
        iota(all(p), 0);
        left.resize(n);
        iota(all(left), 0);
        s.assign(n, 1);
    }
    inline int leader(int x) {
        if (x == p[x])
            return x;
        return p[x] = leader(p[x]);
    }
    inline void merge(int a, int b) {
        a = leader(a);
        b = leader(b);
        if (a == b)
            return;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        left[b] = min(left[b], left[a]);
    }
};

const int maxn = 16;
int tree[maxn * 4];

void upd(int i, int x, int v, int l, int r) {
    if (r - l == 1) {
        tree[v] = x;
    } else {
        int mid = ((r - l) >> 1) + l;
        if (i < mid)
            upd(i, x, 2 * v + 1, l, mid);
        else
            upd(i, x, 2 * v + 2, mid, r);
        tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
    }
}

int get(int lx, int rx, int v, int l, int r) {
    if (lx <= l && r <= rx)
        return tree[v];
    if (r <= lx || rx <= l)
        return 0;
    int mid = ((r - l) >> 1) + l;
    return max(get(lx, rx, 2 * v + 1, l, mid), get(lx, rx, 2 * v + 2, mid, r));
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (auto& elem : a)
        cin >> elem;
    vector<int> perm(n);
    iota(all(perm), 0);
    sort(all(perm), [&a](int l, int r) {
        if (a[l] == a[r])
            return r < l;
        return a[l] < a[r];
        });
    set<int> ind;
    dsu snm;
    snm.init(n);
    for (auto const now : perm) {
        auto it = ind.lower_bound(now);
        if (it != ind.begin()) {
            auto tmp = it;
            --tmp;
            if ((now - *tmp) <= d)
                snm.merge((*tmp), now);
        }
        if (it != ind.end()) {
            auto tmp = it;
            if ((*tmp - now) <= d)
                snm.merge((*tmp), now);
        }
        ind.insert(now);
        int val = 1;
        if (snm.left[snm.leader(now)] != now) {
            val = max(val, get(snm.left[snm.leader(now)], now, 0, 0, maxn) + 1);
        }
        upd(now, val, 0, 0, maxn);
    }
    cout << get(0, maxn, 0, 0, maxn);
    return 0;
}

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