Submission #870147

#	Time	Username	Problem	Language	Result	Execution time	Memory
870147		zwezdinv	Financial Report (JOI21_financial)	C++17	5 / 100	94 ms	8020 KiB

Main

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


using ll = long long;
#define all(x) x.begin(), x.end()

const int N = 3e5;

int tr[2 * N];

void upd(int k, int x) {
    for (k += N, tr[k] = max(tr[k], x); k; k >>= 1, tr[k] = max(tr[k << 1], tr[k << 1 | 1]));
}

int get(int l, int r) {
    l = max(l, 0);
    int res = 0;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, tr[l++]);
        if (~r & 1) res = max(res, tr[r--]);
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, d;
    cin >> n >> d;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = -i;
    }
    sort(a.begin(), a.end());
    for (auto [x, id] : a) {
        id = -id;
        upd(id, get(id - d, id - 1) + 1);
    }
    cout << get(0, n - 1);
}

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