Submission

Score: 100

User: nozmid

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

Language: cpp

Time: 0.291 second

Submitted On: 2026-04-25 14:19:13

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define F first
#define S second

const int maxn = 1e5 + 5;
const int maxu = 1005;
const int inf = 2e9;

struct stc{
	int p, w, t;
	bool operator<(const stc &o) const{
		return p < o.p;
	}
};

int u, k, n;
pii arr[maxn];
stc crys[maxn];
int fw[maxu][maxn];
int res = -inf;

void upd(int i, int val, int t[]){
	for(;i<=n;i+=i&-i) t[i] = max(t[i], val);
}

int qr(int i, int t[]){
	int s = -inf;
	for(;i>0;i-=i&-i) s = max(s, t[i]);
	return s;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> u >> k >> n;
	for(int i=1;i<=n;++i){
		cin >> crys[i].p >> crys[i].w >> arr[i].F;
		arr[i].S = i;
	}
	sort(arr+1, arr+n+1);
	for(int i=1;i<=n;++i) crys[arr[i].S].t = i;
	sort(crys+1, crys+n+1);
	for(int i=1;i<=n;++i){
		auto [np, nu, nt] = crys[i];
		int mx = max(qr(nt, fw[nu]), qr(nt, fw[u]) - k) + 1;
		res = max(res, mx);
		upd(nt, mx, fw[nu]);
		upd(nt, mx, fw[u]);
	}
	cout << res;
}