Submission #1136291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136291		Sharky	Financial Report (JOI21_financial)	C++20	5 / 100	719 ms	63808 KiB

Main

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

struct SegTree {
    int size = 1;
    vector<int> seg, lazy;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 1, 0);
    }
    void update(int pos, int v, int l, int r, int id) {
        if (l == r) {
            seg[id] = max(seg[id], v);
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(pos, v, l, mid, id * 2);
        else update(pos, v, mid + 1, r, id * 2 + 1);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    int query(int ql, int qr, int l, int r, int id) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return seg[id];
        int mid = (l + r) / 2;
        return max(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
    int find(int ql, int qr, int l, int r, int id) {
        if (!seg[id]) return -1;
        if (qr < l || r < ql) return -1;
        if (l == r && seg[id]) return l;
        if (l == r) return -1;
        int mid = (l + r) / 2;
        int res = find(ql, qr, mid + 1, r, id * 2 + 1);
        if (res == -1) return find(ql, qr, l, mid, id * 2);
        return res;
    }
    int find2(int ql, int qr, int l, int r, int id) {
        if (!seg[id]) return -1;
        if (qr < l || r < ql) return -1;
        if (l == r && seg[id]) return l;
        if (l == r) return -1;
        int mid = (l + r) / 2;
        int res = find(ql, qr, l, mid, id * 2);
        if (res == -1) return find(ql, qr, mid + 1, r, id * 2 + 1);
        return res;
    }
} ST, ST2;

const int N = 3e5 + 1;

struct DSU {
    int p[N], sz[N], lb[N];
    
    void init(int n) {
        for (int i = 1; i <= n; i++) p[i] = lb[i] = i, sz[i] = 1;
    }

    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }

    void merge(int u, int v) {
        // cout << "merge: " << u << " " << v << '\n';
        u = find(u), v = find(v);
        if (u == v) return;
        if (u > v) swap(u, v);
        p[v] = u, lb[v] = lb[u];
    }
} dsu;

map<int, vector<int>> mp;

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> a(n+1);
    vector<int> disc;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        disc.push_back(a[i]);
    }
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(disc.begin(), disc.end(), a[i]) - disc.begin() + 1;
        mp[a[i]].push_back(i);
    }
    debug(a);
    ST.init(n + 1);
    ST2.init(n + 1);
    dsu.init(n);
    vector<int> dp(n + 1, 0);
    for (auto& [val, vec] : mp) {
        for (int& pos : vec) {
            int lp = ST2.find(1, pos-1, 1, n, 1), rp = ST2.find(pos, n, 1, n, 1), l;
            // debug(pos, lp);
            if (lp != -1 && lp + d >= pos) dsu.merge(lp, pos);
            if (rp != -1 && rp + d >= pos) dsu.merge(pos, rp);
            l = max(1LL, min(pos - d, dsu.lb[dsu.find(pos)]));
            dp[pos] = ST.query(l, pos-1, 1, n, 1) + 1; 
            ST2.update(pos, 1, 1, n, 1);
        }
        for (int& pos : vec) ST.update(pos, dp[pos], 1, n, 1);
        for (int i = 1; i < vec.size(); i++) if (vec[i-1] + d >= vec[i]) dsu.merge(vec[i-1], vec[i]);
    }
    debug(dp);
    cout << ST.query(1, n, 1, n, 1) << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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