Submission

Score: 100

User: PakinDioxide

Problemset: ผลึกเวลา (Crystal)

Language: cpp

Time: 0.268 second

Submitted On: 2025-09-24 16:58:18

#include <bits/stdc++.h>

using namespace std;

const int mxU = 1005, mxN = 1e5+5;

int u, k, n;

int fen[mxU][mxN];

void upd(int idx, int x, int U) {
    for (int i = idx; i <= n+5; i += i & -i) fen[U][i] = max(fen[U][i], x);//, cerr << i << '\n';
}

int qr(int idx, int U) {
    int x = 0;
    for (int i = idx; i > 0; i -= i & -i) x = max(x, fen[U][i]);
    return x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> u >> k >> n;
    vector <int> cmp;
    vector <tuple <int, int, int>> a(n);
    for (auto &[z, x, y] : a) cin >> x >> y >> z, cmp.emplace_back(x), y++;
    sort(a.begin(), a.end());
    sort(cmp.begin(), cmp.end());
    // cout << '\n';
    int ans = 0;
    // cout << '\n';
    for (auto &[z, x, y] : a) {
        x = upper_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
        // cerr << x << ' ' << y << ' ' << z << '\n';
        int mx = 0;
        mx = max(mx, qr(x-1, y) + 1);
        mx = max(mx, qr(x-1, u+1) + 1 - k);
        upd(x, mx, y);
        upd(x, mx, u+1);
        ans = max(ans, mx);
    }
    cout << ans << '\n';
    // SUB O(UN)

    // SUB U = 1, k = 0;
    // vector <pair <int, int>> V;
    // for (int i = 0; i < n; i++) {
    //     int x, y, z; cin >> x >> y >> z;
    //     V.emplace_back(z, x);
    // }
    // sort(V.begin(), V.end());
    // vector <int> d;
    // for (auto &[x, e] : V) {
    //     int it = lower_bound(d.begin(), d.end(), e) - d.begin();
    //     if (it == d.size()) d.emplace_back(e);
    //     else d[it] = e;
    // }
    // cout << d.size() << '\n';
}