Submission

Score: 11

User: GGEZLOLx3D

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

Language: cpp

Time: 0.028 second

Submitted On: 2026-03-26 20:38:50

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX 1e15
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,en,mon,k,st,mod=1e9+7,u;
    cin >> u >> k >> n;
    int a,b,c;
    vector<pair<int,pair<int,int>>> vec;
    for(i=0;i<n;i++){
        cin >> a >> b >> c;
        vec.push_back({c,{a,b}});
    }
    sort(vec.begin(),vec.end());
    vector<int> dp(n,0),lis;
    for(i=0;i<n;i++){
        auto it=upper_bound(lis.begin(),lis.end(),vec[i].second.first);
        if(it==lis.end()){
            lis.push_back(vec[i].second.first);
        }
        else{
            int pig=it-lis.begin();
            lis[pig]=vec[i].second.first;
        }
        dp[i]=lis.size();
    }
    cout << dp[n-1];
}
/*
5 18 30
1 2 93 84 2
12 1261 0
LRRRRRRRRRRR

9 12 9
LURURDRUU

7 -4 3
RULUULD

7 2 7 4 9 3 3 5 8
5 2
0 1
2 2
3 6
6 6
9 10
10
15

5 2
0 0
2 0
7 0
-2 0
-1 0
10
3
*/