Submission

Score: 34

User: meme_boi2

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

Language: cpp

Time: 0.109 second

Submitted On: 2026-01-27 00:43:46

#include <bits/stdc++.h>
using namespace std;
int u, k, n,sz=1;
const int MAXN = 1e5+2;
int tree[1001][2*MAXN];
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){
    idx += sz;
    tree[uni][idx] = max(tree[uni][idx],val);
    idx /= 2;
    while(idx > 0){
        tree[uni][idx] = max(tree[uni][2*idx],tree[uni][2*idx+1]);
        idx /= 2;
    }
}
int query(int p,int l,int r){
    int ans = 0 ;
    l += sz; r+= sz;
    while(l <= r){
        if(l%2 == 1){
            ans = max(ans,tree[p][l]);
            l++;
        }
        if(r%2 == 0){
            ans = max(ans,tree[p][r]);
            r--;
        }
        l/=2; r/= 2;
    }
    return ans;
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> u >> k >> n;
    while(sz < n) sz*=2;
    // 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;
    }
    int LIS = 1;
    update(get<1>(mat[0]),mp[get<0>(mat[0])],1);
    update(u,mp[get<0>(mat[0])],1);
    for(int i = 1; i < n; i++){
        int x = query(get<1>(mat[i]),0,mp[get<0>(mat[i])]-1), xx = query(u,0,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
*/