Submission

Score: 100

User: Dormon

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

Language: cpp

Time: 0.297 second

Submitted On: 2025-06-22 21:27:15

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

const int N = 1e5 + 10, U = 1e3 + 5, K = 1e3 + 5;
int u, k, n, ans;
vector<tuple<int, int, int>> crys;
vector<int> compress;
map<int, int> cmp;

struct FenwickTree{
  int fw[N] = {0};
  void upd(int i, int v){
    for(; i < N; i += (i&-i)) fw[i] = max(fw[i], v);
  }
  int qry(int i, int mx = 0){
    for(; i > 0; i -= (i&-i)) mx = max(mx, fw[i]);
    return mx;
  }
}ftree[U];

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> u >> k >> n;
  crys.resize(n);
  for(auto &[t, p, w]:crys) cin >> p >> w >> t, compress.push_back(p);
  sort(crys.begin(), crys.end());
  sort(compress.begin(), compress.end());
  compress.erase(unique(compress.begin(), compress.end()), compress.end());
  for(int i = 0; i < compress.size(); ++i) cmp[compress[i]] = i + 1;
  for(auto [t, p, w]:crys){
    int i = cmp[p];
    int cal = ftree[w].qry(i - 1) + 1;
    cal = max(cal, ftree[U - 1].qry(i - 1) - k + 1);
    ans = max(ans, cal);
    ftree[w].upd(i, cal);
    ftree[U - 1].upd(i, cal);
  }
  cout << ans;
}