Submission

Score: 100

User: hyyh

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

Language: cpp

Time: 1.342 second

Submitted On: 2026-03-14 22:04:19

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <tuple>
#include <math.h>
#include <cstring>
#include <bitset>
#include <set>
#include <map>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;

#define endl '\n'
#define f first
#define s second
#define all(x) begin(x),end(x)

int main(){
    int u;cin >> u;
    int k;cin >> k;
    int n;cin >> n;
    vector<vector<int>> vc(u+1);
    for(int i{};i <= u;i++){
        vc[i].emplace_back(0);
    }
    vector<piii> inp;
    for(int i{};i < n;i++){
        int a,b,c;cin >> a >> b >>  c;
        inp.emplace_back(c,b+1,a);
    }
    sort(all(inp));
    for(auto [time,uni,power]:inp){
        // for(int i{};i <= u;i++){
        //     for(auto k:vc[i]) cout << k << " ";
        //     cout << endl;
        // }
        // cout << "________" << endl;
        auto it1 = lower_bound(all(vc[uni]),power);
        auto it2 = lower_bound(all(vc[0]),power)-vc[0].begin()-k+1;
        int itind = it1-vc[uni].begin();
        int ind = 0;
        if(it1 == vc[uni].end()){
            vc[uni].emplace_back(power);
            ind = vc[uni].size()-1;
        }
        else{
            *it1 = power;
            ind = it1-vc[uni].begin();
        }
        while(int(it2) > itind){
            //cout << it2 << "-" << itind << " " << vc[uni].size() << endl;
            if(itind == vc[uni].size()) vc[uni].emplace_back(power);
            else{
                if(vc[uni][itind] < power) itind = it2;
                else vc[uni][itind] = power;
            }
            ind = max(ind,itind);
            itind++;
        }
        if(ind >= vc[0].size()) vc[0].emplace_back(power);
        else vc[0][ind] = min(vc[0][ind],power);
    }
    cout << vc[0].size()-1;
}
/*
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

5
____
2 2 10
2 1 1
5 1 2
7 1 3
3 1 4
8 0 5
9 0 6
1 0 7
10 0 8
13 0 9
4 0 10

5
*/