Submission

Score: 100

User: KantaponZ

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

Language: cpp

Time: 0.298 second

Submitted On: 2025-06-27 00:04:13

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxU = 1005, maxN = 100005;
int U, k, N;

tuple<int,int,int> pos[maxN]; // t, w, p
set<int> srt;
unordered_map<int,int> x;

struct Fenwick {
    int a[maxN];
    
    int query(int i) {
        int res = 0;
        while (i > 0) {
            res = max(res, a[i]);
            i -= (i & -i);
        }
        return res;
    }

    void update(int i, int val) {
        while (i < maxN) {
            a[i] = max(a[i], val);
            i += (i & -i);
        }
    }
} fenw[maxU];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> U >> k >> N;

    for (int i = 0; i < N; i++) {
        int p, w, t;
        cin >> p >> w >> t;
        pos[i] = {t, w, p};
        srt.insert(p);
    }

    vector<int> temp(srt.begin(), srt.end());
    for (int i = 0; i < temp.size(); i++) {
        x[temp[i]] = i + 1;
    }

    sort(pos, pos + N);

    int ans = 0;

    for (int i = 0; i < N; i++) {
        auto [t, w, pp] = pos[i];
        int p = x[pp];

        int x1 = fenw[w].query(p - 1) + 1;
        int x2 = fenw[1001].query(p - 1) + 1 - k;
        int x = max(x1, x2);

        fenw[w].update(p, x);
        fenw[1001].update(p, x);
        
        ans = max(ans, x);
    }

    cout << ans;


}