Submission

Score: 11

User: njoop

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

Language: cpp

Time: 1.523 second

Submitted On: 2025-05-23 18:05:56

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define MAXN 200005
#define MOD (int)(1e9+7)
#define INF (int)1e17
#define enl '\n'
#define int long long
#define DB(code) cout<<'\t'<<code<<'\n';
#define SP <<' '<<
using namespace std;
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int m,k,n;
    cin >> m >> k >> n;
    pair<int,pii> arr[n]; // {time,{lane,val}}
    for(int i=0; i<n; i++) cin >> arr[i].s.s >> arr[i].s.f >> arr[i].f;
    sort(arr,arr+n);
    vector<int> val[m];
    for(int i=0; i<n; i++){
        pii c=arr[i].s;
        int pos=upper_bound(val[c.f].begin(),val[c.f].end(),c.s)-val[c.f].begin();
        if(pos>=val[c.f].size()) val[c.f].pb(c.s);
        else val[c.f][pos]=c.s;
        for(int j=0; j<m; j++) if(j!=c.f){
            if(pos-k>=0 && pos-k<val[j].size()) val[j][pos-k]=min(val[j][pos-k],c.s);
            else if(pos-k>=val[j].size()) val[j].pb(c.s);
        }
    }
    int ans=0;
    for(int i=0; i<m; i++) ans=max(ans,(int)val[i].size());
    cout << ans;
	return 0;
}
// O(n(logn+m))
/*

2 2 9
3 1 11
4 1 21
5 1 31
11 1 61
20 1 71
8 2 42
2 2 52
10 2 62
50 2 72

*/