Submission

Score: 100

User: mydKN

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

Language: cpp

Time: 0.282 second

Submitted On: 2025-06-11 00:21:03

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")

using namespace std;

const int maxn = 1e5 + 5;
const int maxu = 1005;

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

struct FW{
	int tr[maxn] = {};
	void update(int i, int val){
		for(;i<maxn;i+=i&-i) tr[i] = max(tr[i], val);
	}
	int query(int i){
		int mx = 0;
		for(;i>0;i-=i&-i) mx = max(mx, tr[i]);
		return mx;
	}
};

int u, k, n;
stc crys[maxn];
vector<int> vec;
map<int, int> compr;
int res = 0;
FW fw[maxu];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> u >> k >> n;
	vec.reserve(n);
	for(int i=0;i<n;++i){
		cin >> crys[i].p >> crys[i].w >> crys[i].t;
		vec.emplace_back(crys[i].p);
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	sort(crys, crys+n);
	for(int i=0;i<vec.size();++i){
		compr[vec[i]] = i+1;
	}
	for(int i=0;i<n;++i){
		int p = crys[i].p, w = crys[i].w, t = crys[i].t, compp = compr[p];
		int mx = fw[w].query(compp - 1) + 1;
		mx = max(mx, fw[maxu-1].query(compp - 1) - k + 1);
		res = max(res, mx);
		fw[maxu-1].update(compp, mx);
		fw[w].update(compp, mx);
	}
	cout << res;
}