Submission

Score: 100

User: NovemNotes

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

Language: cpp

Time: 0.684 second

Submitted On: 2026-04-24 15:18:59

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

#define int long long

int u,k,n,ans;
vector<tuple<int,int,int>> v;

struct fenwick{
    int n;
    vector<int> v;
    fenwick(int sz){
        n = sz;
        v.assign(n+9,0);
    }
    void update(int i,int val){
        for(;i<=n;i+=i&-i)v[i] = max(v[i],val);
    }
    int query(int i){
        int ans=0;
        for(;i>0;i-=i&-i)ans = max(ans,v[i]);
        return ans;
    }
};

vector<int> co;
int encode(int x){
    int idx = lower_bound(co.begin(),co.end(),x)-co.begin()+1;
    return idx;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> u >> k >> n;
    for(int i=0;i<n;i++){
        int p,w,t;cin >> p >> w >> t;
        v.emplace_back(p,w,t);
        co.emplace_back(p);
    }
    sort(v.begin(),v.end(),[](const auto &a,const auto &b){
        return get<2>(a) < get<2>(b);
    });
    sort(co.begin(),co.end());
    co.erase(unique(co.begin(),co.end()),co.end());
    vector<fenwick> tree(u,fenwick(co.size()+1));
    fenwick gtree(co.size()+1);
    for(auto &[p,w,t]:v){
        //query มิติตัวเอง
        int q = tree[w].query(encode(p)-1)+1;
        //query มิติคนอื่น
        int nq = gtree.query(encode(p)-1)-k+1;
        // cout << p << " " << w << " " << t << " " << q << " " << nq << "\n";
        int ok = max(nq,q);
        ans = max(ans,ok);
        tree[w].update(encode(p),ok);
        gtree.update(encode(p),ok);
    }
    cout << ans << "\n";
    return 0;
}
/*
3 0 13
2 0 1
1 1 2
4 0 3
20 0 10
12 2 4
7 1 5
14 2 6
3 1 7
11 2 12
9 1 8
10 2 11
25 0 13
13 2 20
*/