제출 #1226110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226110		Nailuj_217	Financial Report (JOI21_financial)	C++20	100 / 100	744 ms	88364 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll LEN = 300005;

array<ll, LEN> custom_d;
//      parent max
array<pair<ll, ll>, LEN> parent;
set<ll> unifind;

array<ll, LEN*5> tree;
array<multiset<ll>, LEN> dps;

ll insert_at(ll i, ll s, ll f, ll v, ll a) {
    if (v < s || v > f) return tree[i];
    if (s == f) {
        dps[s].insert(a);
        return tree[i] = *(--dps[s].end());
    }
    return tree[i] = max(
        insert_at(i*2, s, (s+f)/2, v, a), 
        insert_at(i*2+1, (s+f)/2+1, f, v, a)
    );
}

ll remove_at(ll i, ll s, ll f, ll v, ll a) {
    if (v < s || v > f) return tree[i];
    if (s == f) {
        dps[s].erase(dps[s].find(a));
        if (dps[s].empty()) return tree[i] = 0;
        return tree[i] = *(--dps[s].end());
    }
    return tree[i] = max(
        remove_at(i*2, s, (s+f)/2, v, a), 
        remove_at(i*2+1, (s+f)/2+1, f, v, a)
    );
}

ll query(ll i, ll s, ll f, ll a, ll b) {
    if (s > b || f < a) return 0;
    if (s >= a && f <= b) return tree[i];
    return max(
        query(i*2, s, (s+f)/2, a, b), 
        query(i*2+1, (s+f)/2+1, f, a, b)
    );
}


ll d;

pair<ll, ll> get_parent(ll a) {
    if (parent[a].first == a) return parent[a];
    return parent[a] = get_parent(parent[a].first);
}

void merge(ll a, ll b) {
    a = get_parent(a).first;
    b = get_parent(b).first;
    if (a == b) return;

    parent[b].first = a;
    parent[a].second = max(parent[a].second, parent[b].second);
}


void insert(ll i) {
    parent[i] = {i, i};
    unifind.insert(i);

    auto it = unifind.find(i);
    if (it != unifind.begin() && abs(*(--it) - i) <= d) {
        merge(i, *it);
    }
    it = unifind.find(i);
    if (++it != unifind.end() && abs(*it - i) <= d) {
        merge(i, *it);
    }

}


void compress(vector<ll> &r) {
    vector<pair<ll, ll>> temp;
    for (int i = 0; i < r.size(); i++) {
        temp.push_back({r[i], i});
    }
    sort(temp.begin(), temp.end());
    ll cur = 1;
    for (int i = 0; i < r.size();) {
        ll j = i;
        while (i < r.size() && temp[j].first == temp[i].first) {
            r[temp[i].second] = cur;
            i++;
        }
        cur ++;
    }
}


array<vector<pair<ll, ll>>, LEN*2+5> ins;


int main() {

    // freopen("input.in", "r", stdin);

    ll n;
    cin >> n >> d;
    vector<ll> r(n+1);
    for (int i = 1; i <= n; i++) cin >> r[i];

    compress(r);

    vector<pair<ll, ll>> sorted;
    for (int i = 1; i <= n; i++) sorted.push_back({r[i], -i});
    sort(sorted.begin(), sorted.end());

    for (auto [val, index]: sorted) {
        index*=-1;
        insert(index);
        custom_d[index] = get_parent(index).second;
    }
    ll mxdp = 0;
    for (int i = 1; i <= n; i++) {
        for (auto [where, what]: ins[i]) {
            remove_at(1, 1, n, where, what);
        }
        ll dpval = query(1, 1, n, 1, r[i] - 1) + 1;
        mxdp = max(mxdp, dpval);
        ins[custom_d[i] + 1 + d].push_back({r[i], dpval});
        insert_at(1, 1, n, r[i], dpval);
        
    }

    cout << mxdp << 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