Submission

Score: 100

User: Zonezonee

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

Language: cpp

Time: 0.256 second

Submitted On: 2026-04-04 12:19:30

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, U = 1e3+10;

struct fw{
    int fw[N];
    void upd(int idx, int val){
        for(; idx < N; idx += idx&(-idx)) fw[idx] = max(fw[idx], val);
    }
    int query(int idx){
        int res = 0;
        for(; idx > 0; idx -= idx&(-idx)) res = max(res, fw[idx]);
        return res;
    }
} f[U];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int u, k, n;
    cin >> u >> k >> n;
    vector<tuple<int, int, int>> v;
    vector<int> c;
    for(int i = 1; i <= n; ++i){
        int p, w, t;
        cin >> p >> w >> t;
        v.push_back({t, p, w});
        c.push_back(p);
    }
    sort(c.begin(), c.end());
    sort(v.begin(), v.end());
    int ans = 0;
    for(auto [ignore, p, w] : v){
        p = lower_bound(c.begin(), c.end(), p) - c.begin() + 1;
        int sz = f[w].query(p) + 1;
        sz = max(sz, f[U-1].query(p) - k + 1);
        ans = max(ans, sz);
        f[w].upd(p, sz);
        f[U-1].upd(p, sz);
    }
    cout << ans << '\n';
}