二分做法

#include<bits/stdc++.h>
#define ZY 0;
using namespace std;
const int N = 1e5+10;
int n, T, ans, cnt;

struct Node {
	int a, b, c, d;
} e[N];

bool cmp(Node a, Node b) {
	if (a.a != b.a) return a.a < b.a;
	return a.b < b.b;
}

bool check(int k) {
	for (int i = 1; i <= n; i++) {
		if (e[i].a <= k) k += e[i].c;
		else return 0;
	}
	return 1;
}

bool operator <(Node a, Node b) {
	return a.b > b.b;
}

priority_queue<Node> q;

int main() {
	scanf("%d %d", &T, &n);
	for (int i = 1; i <= n; i++)
		scanf("%d %d %d %d", &e[i].a, &e[i].b, &e[i].c, &e[i].d);
	sort(e + 1, e + 1 + n, cmp);
//	for(int i=1;i<=n;i++)
//		printf("%d %d\n",e[i].a,e[i].b);
	int L = 0, R = 1e9;
	while (L < R) {
		int mid = (L + R) >> 1;
		if (check(mid)) R = mid;
		else L = mid + 1;
	}
	int i = 1;
	int k = R;
	while (i <= n) {
		while (i <= n && k >= e[i].a)
			q.push(e[i++]);
		while (!q.empty()) {
			Node u = q.top();
			q.pop();
			k += u.c;
			while (i <= n && k >= e[i].a)
				q.push(e[i++]);
			if (u.b > ans) {
				cnt += u.b - ans;
				ans = u.b;
			}
			ans += u.d;
		}
	}
	printf("%d %d", R, cnt);
	return ZY;
}

WA