1260D - A Game with Traps - CodeForces Solution

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+3;
int m,n,k,t,a[N];
vector<pair<int ,int >>sum[N];
bool check(int mid) {
    int ans=0,now=0;
	for(int i=1;i<=n;i++) {
		for(auto [x,y]: sum[i]) 
			if(y>a[mid]) now=max(now,x);
        if(i<=now) ans+=2;
	}
	if(ans+n+1<=t) return 1;
	else return 0;
}
void solve() {
	cin>>m>>n>>k>>t;
	for(int i=1; i<=m; i++) cin>>a[i];
	for(int i=1; i<=k; i++) {
		int l,r,x;
		cin>>l>>r>>x;
		sum[l].push_back({r,x});
	}
	sort(a+1,a+m+1,greater<int>());
    a[0]=1e9;
	int l=0,r=m;
	while(l<r) {
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	int t;	cin>>t;	while(t--)
	solve();
	return 0;
}