Submission #541315

#	Time	Username	Problem	Language	Result	Execution time	Memory
541315		Jomnoi	Financial Report (JOI21_financial)	C++17	5 / 100	302 ms	12368 KiB

Main

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

const int N = 3e5 + 10;
const int INF = 1e9 + 7;

int a[N];
int dp[N];

class SegmentTree {
private :
    int tree[4 * N];
public :
    void update(int idx, int l, int r, int q, int k) {
        if(r < q or q < l) {
            return;
        }
        if(l == r) {
            tree[idx] = k;
            return;
        }

        int mid = (l + r) / 2;
        update(idx * 2, l, mid, q, k);
        update(idx * 2 + 1, mid + 1, r, q, k);
        tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
    }

    int query(int idx, int l, int r, int ql, int qr) {
        if(r < ql or qr < l) {
            return 0;
        }
        if(ql <= l and r <= qr) {
            return tree[idx];
        }

        int mid = (l + r) / 2;
        return max(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
    }
}ST;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, d;
    cin >> n >> d;
    vector <pair <int, int>> vec;
    vec.emplace_back(-INF, 0);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        vec.emplace_back(a[i], i);
    }
    sort(vec.begin(), vec.end());

    for(int i = 1; i <= n; i++) {
        int need = lower_bound(vec.begin(), vec.end(), make_pair(a[i], -1)) - vec.begin();
        int now = lower_bound(vec.begin(), vec.end(), make_pair(a[i], i)) - vec.begin();

        if(i - d - 1 > 0) {
            int prv = lower_bound(vec.begin(), vec.end(), make_pair(a[i - d - 1], i - d - 1)) - vec.begin();
            ST.update(1, 1, n, prv, 0);
        }

        dp[i] = ST.query(1, 1, n, 1, need - 1) + 1;
        ST.update(1, 1, n, now, dp[i]);
    }
    cout << ST.query(1, 1, n, 1, n);
    return 0;
}

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