今天的一场虚拟竞赛
就是一道贪心+模拟
不难，但是wa了好多发。果然还是没有适应这个难度的题目啊

题目让我们求最大可以带走的军队数量。
很显然，我们能够想到二分。
我们从属性值最高的兵开始带走，可以只考虑带的兵中属性值最低的那个人。
所以，我们只需要排个序就行了。
关键是二分中如何二分呢？如何判断，这个属性值可以在规定时间内度过呢？
check()函数是关键！
我们想想哈，假设我的军队走到了1出，发现2处有陷阱，且可以杀死我的军队中最弱的那个人。
那么，身为司令官的我肯定要先去拆除那个陷阱。
假设我需要走到5处才能拆除那个陷阱，那么自然在从2到5这一路，我会把我能拆的陷阱都给拆了。然后我再跑回来带领军队前进

ok，那么我们走到了2，发现3处还有一处有威胁的陷阱，要到才能拆掉他，于是司令我又要跑到6去拆掉这个陷阱。
等等！为什么我们不在刚才跑到5处时再多跑一下，拆掉那个陷阱呢？！
那么，判断司令我还向不向前走的依据是什么呢？
下面给出归纳的结论：
司令我啊，一路向前走拆炸弹，如果我的身后还会有能对我的军队造成威胁的陷阱，那么我就会一直走下去，拆除炸弹。
直到后面没有能再威胁到军队的陷阱，我就回到军队带领军队前进！

ok，这样模拟就行了！！！
但是实际执行起来还是有一定的难度的。

#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
const int max_n = 2e5+100;
ll m,n,k,t;
int a[max_n];
vector<int> b[max_n];
vector<int> c[max_n];
bool vis[max_n];
struct trap{
    int l,r,d;
}tr[max_n];
bool check(int mid){
    ll cct = 0;
    if (mid==0)return true;
    int condi = a[mid];
    for (int i=1;i<=k;++i)
        if (tr[i].d<=condi)vis[i]=1;
        else vis[i]=0;
    int i=0,j=0;int to=0;
    for (j=0;j<n;){
        for (int id:b[j+1]){
            if (vis[id])continue;
            else to = max(tr[id].r,to);
        }while (to!=i){
            ++i;
            for (int id:c[i])vis[id]=1;
            for (int id:b[i])if (!vis[id])to=max(to,tr[id].r);
        }
        if (i==j){
            ++cct;++i;++j;++to;
        }
        else{
            cct+=((ll)i-(ll)j)*(ll)3;
            j=i;
        }
    }
    return cct<t;
}

int Solve(){
    int l = 0,r = m;
    int ans = 0;
    while (l<=r){
        int mid = (l+r)>>1;
        if (check(mid)){
            l = mid+1;
            ans = max(ans,mid);
        }
        else r = mid-1;
    }return ans;
}

int main(){
    scanf("%lld %lld %lld %lld",&m,&n,&k,&t);
    for (int i=1;i<=m;++i)scanf("%d",&a[i]);
    for (int i=1;i<=k;++i)scanf("%d %d %d",&tr[i].l,&tr[i].r,&tr[i].d);
    for (int i=1;i<=k;++i){
        b[tr[i].l].push_back(i);
        c[tr[i].r].push_back(i);
    }
    sort(a+1,a+1+m,greater<int>());
    printf("%d\n",Solve());
}