题解 | 【入门班】借教室

#include <iostream>
#include <vector>

using namespace std;

const int N = (int) 1e6 + 5;

bool judge(long long diff[], int n,const vector<vector<int> >& orders, int m) {
	long long* diff2 = new long long[n + 2];
	copy(diff, diff + n + 2, diff2);
	for (int i = 1; i <= m; i++) {
		diff2[orders[i][1]] += -orders[i][0];
		diff2[orders[i][2] + 1] -= -orders[i][0];
	}
	long long sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += diff2[i];
		if (sum < 0) return false;	
	}
	return true;
}

int main() {
	int n, m;
	cin >> n >> m;
	int* a = new int[n + 1];
  	//注意精度
	long long* diff = new long long[n + 2];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		diff[i] = i > 1 ? a[i] - a[i - 1] : a[i]; 
	}
  	//直接使用栈存储数组会stackoverflow
	vector<vector<int> > orders(m + 1, vector<int>(3)); 
	for (int i = 1; i <= m; i++) {
		cin >> orders[i][0] >> orders[i][1] >> orders[i][2];
	}
	if (judge(diff, n, orders, m)) {
		cout << 0 << endl;
	} else{
		int l = 1, r = m;
		while (r > l) {
			int mid = (r - l) / 2 + l;
			if (judge(diff, n, orders, mid)) l = mid + 1;
			else r = mid; 
		}
		cout << l << endl;	
	} 
}