Submission

Score: 100

User: meme_boi2

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

Language: cpp

Time: 1.142 second

Submitted On: 2026-03-22 10:04:46

#include <bits/stdc++.h>
using namespace std;
#define int long long
int u, k, n,sz=1;
const int MAXN = 1e5+2;
vector<vector<int>> tree(1001,vector<int>(MAXN,0));
map<int,int> mp;
bool cmp(tuple<int,int,int> a,tuple<int,int,int> b){
    return get<2>(a) < get<2>(b);
}
void update(int uni,int idx, int val){
    for(; idx <= n; idx += idx&-idx){
        tree[uni][idx] = max(tree[uni][idx],val);
    }
}
int query(int p,int idx){
    int ans = 0 ;
    for(; idx > 0; idx -= idx&-idx){
        ans = max(tree[p][idx],ans);
    }
    return ans;
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> u >> k >> n;
    
    // w p t
    vector<int> tmp;
    vector<tuple<int,int,int>> mat;
    for(int i = 0; i < n; i++){
        int w,p,t;
        cin >> w >> p >> t;
        mat.push_back(make_tuple(w,p,t));
        tmp.push_back(w);
    }
    sort(mat.begin(),mat.end(),cmp);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(int i =0;i < tmp.size(); i++){
        mp[tmp[i]] = i +1 ;
    }
    int LIS = 0;
  //  update(get<1>(mat[0]),mp[get<0>(mat[0])],1);
   // update(u,mp[get<0>(mat[0])],1);
    for(int i = 0; i < n; i++){
        int x = query(get<1>(mat[i]),mp[get<0>(mat[i])]-1), xx = query(u,mp[get<0>(mat[i])]-1);
     
        update(get<1>(mat[i]),mp[get<0>(mat[i])],max(x+1,xx+1-k));
        update(u,mp[get<0>(mat[i])],max(x+1,xx+1-k));

        LIS = max(LIS,max(x+1,xx+1-k));
    }
    cout << LIS;
}
/*
3 1 13
2 0 1
1 1 2
4 0 3
20 0 10
12 2 4
7 1 5
14 2 6
3 1 7
11 2 12
9 1 8
10 2 11
25 0 13
13 2 20
*/