Submission #534422

#	Time	Username	Problem	Language	Result	Execution time	Memory
534422		Monarchuwu	Financial Report (JOI21_financial)	C++17	100 / 100	531 ms	37872 KiB

Main

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 3e5 + 7, inf = 0x3f3f3f3f;
int n, d;
int a[N];

int b[N];
void compress() {
    copy(a + 1, a + n + 1, b + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}

priority_queue<pii> q[N];
int seg[1 << 20], laz[1 << 20], mi[1 << 20];

void del(int u, int l, int r, int tme) {
    if (mi[u] >= tme) return;
    if (l == r) {
        while (!q[l].empty() && q[l].top().ss < tme) q[l].pop();

        if (q[l].empty()) {
            seg[u] = 0;
            mi[u] = inf;
        }
        else {
            seg[u] = q[l].top().ff;
            mi[u] = max(laz[u], q[l].top().ss);
        }
        return;
    }
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    del(u1, l, m, tme);
    del(u2, m + 1, r, tme);

    seg[u] = max(seg[u1], seg[u2]);
    mi[u] = max(laz[u], min(mi[u1], mi[u2]));
}

int get(int u, int l, int r, int p) {
    if (r <= p) return seg[u];
    if (p < l) return 0;
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    return max(get(u1, l, m, p), get(u2, m + 1, r, p));
}

void add(int u, int l, int r, int p, pii v) {
    if (l == r) {
        q[l].push(v);
        seg[u] = q[l].top().ff;
        mi[u] = max(laz[u], q[l].top().ss);
        return;
    }
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    if (p <= m)
        add(u1, l, m, p, v);
    else add(u2, m + 1, r, p, v);

    seg[u] = max(seg[u1], seg[u2]);
    mi[u] = max(laz[u], min(mi[u1], mi[u2]));
}

void upd(int u, int l, int r, int p, int tme) {
    if (r < p) return;
    if (p <= l) return void(laz[u] = mi[u] = tme);
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    upd(u1, l, m, p, tme);
    upd(u2, m + 1, r, p, tme);
}

int dp[N];
void solve() {
    memset(mi, 0x3f, sizeof(mi));
    for (int i = 1; i <= n; ++i) {
        del(1, 1, n, i - d);
        dp[i] = get(1, 1, n, a[i] - 1) + 1;
        add(1, 1, n, a[i], pii(dp[i], i));
        upd(1, 1, n, a[i], i);
    }
    cout << *max_element(dp, dp + n + 1) << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    compress();

    solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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