Submission

Score: 100

User: exoworldgd

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

Language: cpp

Time: 0.390 second

Submitted On: 2025-11-09 00:17:08

#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define int long long
using namespace std;
const int inf = LLONG_MAX, mod = 1e9+7, maxn = 1e5+5;
int fen[1005][maxn];
signed main(void) {
    exoworldgd;
    int u,k,n,res=0;
    cin >> u >> k >> n;
    tuple<int,int,int> a[n];
    vector<int> v;
    map<int,int> cmp;
    for (auto& [r,p,q] : a) cin >> p >> q >> r, v.push_back(p);
    sort(a,a+n), sort(v.begin(),v.end()), v.erase(unique(v.begin(),v.end()),v.end());
    for (int i = 0; i < v.size(); i++) cmp[v[i]] = i+1;
    for (auto [r,p,q] : a) {
        int idx = cmp[p], mx=0, temp=0;
        for (int i = idx-1; i > 0; i -= i&-i) mx = max(mx,fen[q][i]);
        for (int i = idx-1; i > 0; i -= i&-i) temp = max(temp,fen[u][i]);
        mx = max(mx+1, temp >= k ? temp+1-k : 0);
        for (int i = idx; i <= v.size(); i += i&-i) fen[q][i] = max(fen[q][i],mx);
        for (int i = idx; i <= v.size(); i += i&-i) fen[u][i] = max(fen[u][i],mx);
        res = max(res,mx);
    }
    cout << res;
}