Submission

Score: 20

User: foldnut

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

Language: cpp

Time: 0.132 second

Submitted On: 2025-11-10 20:11:51

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e5;
struct segtree{
    struct node{
        int v;
        node *l, *r;
        node(int v) : v(v), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt = 0;
    void upd(ll l, ll r, pnode &k, int x, ll pos){
        if(!k) k = new node(0);
        if(l == r) return k->v = x, void();
        ll md = (l + r) / 2;
        if(pos <= md) upd(l, md, k->l, x, pos);
        else upd(md + 1, r, k->r, x, pos);
        k->v = max(k->l ? k->l->v : 0, k->r ? k->r->v : 0);
    }
    int qry(ll l, ll r, ll ql, ll qr, pnode k){
        if(qr < l || r < ql || !k) return 0;
        if(ql <= l && r <= qr) return k->v;
        ll md = (l + r) / 2;
        return max(qry(l, md, ql, qr, k->l), qry(md + 1, r, ql, qr, k->r));
    }
}s1, s2;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int u, k, n;
    cin >> u >> k >> n;
    vector<tuple<ll, ll, ll>> v(n);
    map<ll, ll> mp;
    for(int i = 0;i<n;i++){
        auto &[t, p, w] = v[i];
        cin >> p >> w >> t;
        mp[p] = 0;
    }
    int cnt = 0;
    for(auto &[x, y] : mp){
        y = cnt++;
    }
    sort(v.begin(), v.end());
    for(auto &[t, p, w] : v){
        p = mp[p];
    }
    vector<int> dp(n);
    for(int i = 0;i<n;i++){
        dp[i] = 1;
        auto [t, p, w] = v[i];
        dp[i] = max(dp[i], 1 + s1.qry(0, 1000 * N - 1, w * N, w * N + p - 1, s1.rt)); //same unv
        dp[i] = max(dp[i], 1 - k + s2.qry(0, 1000 * N - 1, 0, N * p - 1, s2.rt));
        s1.upd(0, 1000 * N - 1, s1.rt, dp[i], w * N + p);
        s2.upd(0, 1000 * N - 1, s2.rt, dp[i], p * N + w);
    }
    cout << *max_element(dp.begin(), dp.end());
}