제출 #894915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894915		Alcabel	Financial Report (JOI21_financial)	C++17	100 / 100	1698 ms	293708 KiB

Main

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

struct Cell {
    int len, pref, suf, ans;
    Cell() {len = 0, pref = 0, suf = 0, ans = 0;}
    Cell operator+(const Cell& other) const {
        Cell res;
        res.len = len + other.len;
        res.pref = pref;
        if (pref == len) { res.pref += other.pref; }
        res.suf = other.suf;
        if (other.suf == other.len) { res.suf += suf; }
        res.ans = max(suf + other.pref, max(ans, other.ans));
        return res;
    }
    ~Cell() {}
};

struct TreeSeg {
    int n, N;
    vector<Cell> st;
    TreeSeg() {}
    TreeSeg(int _n) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        st.resize(2 * N);
        for (int i = 0; i < n; ++i) {
            st[N + i].len = 1;
        }
        for (int i = N - 1; i > 0; --i) {
            st[i].len = st[2 * i].len + st[2 * i + 1].len;
        }
    }
    void turn(int v, int tl, int tr, int i) {
        if (tl + 1 == tr) {
            st[v].pref = st[v].suf = st[v].ans = 1;
            return;
        }
        int m = tl + (tr - tl) / 2;
        if (i >= m) {
            turn(2 * v + 1, m, tr, i);
        } else {
            turn(2 * v, tl, m, i);
        }
        st[v] = st[2 * v] + st[2 * v + 1];
    }
    void turn(int i) {
        turn(1, 0, N, i);
    }
    Cell curLeft;
    int getSeg(int v, int tl, int tr, int l, int d) {
        if (tr <= l) {
            return tr;
        }
        if (tl >= l && (curLeft + st[v]).ans < d) {
            curLeft = curLeft + st[v];
            return tr;
        }
        if (tl + 1 == tr) {
            return tl;
        }
        int m = tl + (tr - tl) / 2;
        int res = getSeg(2 * v, tl, m, l, d);
        if (res == m) {
            res = getSeg(2 * v + 1, m, tr, l, d);
        }
        return res;
    }
    int getSeg(int l, int d) {
        curLeft.len = curLeft.pref = curLeft.suf = curLeft.ans = 0;
        return getSeg(1, 0, N, l, d);
    }
    ~TreeSeg() {}
};

struct TreeDP {
    int n, N;
    vector<set<pair<int, int>>> st;
    TreeDP() {}
    TreeDP(int _n) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        st.resize(2 * N);
    }
    void insert(int v, int tl, int tr, int l, int r, int key, int val) {
        if (tl >= r || tr <= l) {
            return;
        }
        if (l <= tl && tr <= r) {
            pair<int, int> cur = {key, n + 10};
            auto it = st[v].upper_bound(cur);
            cur.second = val;
            if (it == st[v].begin() || prev(it)->second < val) {
                while (it != st[v].end() && it->second <= val) {
                    it = st[v].erase(it);
                }
                st[v].insert(cur);
            }
            return;
        }
        int m = tl + (tr - tl) / 2;
        insert(2 * v, tl, m, l, r, key, val);
        insert(2 * v + 1, m, tr, l, r, key, val);
    }
    void insert(int l, int r, int key, int val) {
        if (l >= r) {
            return;
        }
        insert(1, 0, N, l, r, key, val);
    }
    int query(int v, int tl, int tr, int i, int x) {
        int res = 0;
        auto it = st[v].lower_bound(make_pair(x, -1));
        if (it != st[v].begin()) {
            res = prev(it)->second;
        }
        if (tl + 1 < tr) {
            int m = tl + (tr - tl) / 2;
            if (i < m) {
                res = max(res, query(2 * v, tl, m, i, x));
            } else {
                res = max(res, query(2 * v + 1, m, tr, i, x));
            }
        }
        return res;
    }
    int query(int i, int x) {
        return query(1, 0, N, i, x);
    }
    ~TreeDP() {}
};

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> a(n), order(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        order[i] = i;
    }
    sort(order.begin(), order.end(), [&](const int& A, const int& B) {
        return make_pair(-a[A], A) < make_pair(-a[B], B);
    });
    TreeSeg aux(n);
    vector<int> border(n);
    for (const int& i : order) {
        border[i] = aux.getSeg(i + 1, d);
        aux.turn(i);
    }
    TreeDP st(n);
    vector<int> dp(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        dp[i] = st.query(i, a[i]) + 1;
        st.insert(i + 1, min(border[i] + 1, n), a[i], dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    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