AcWing 503. 借教室
原题链接
简单
作者:
again_1
,
2024-03-04 20:00:36
,
所有人可见
,
阅读 19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
#define ll long long
ll r[N], d[N], differ[N];
int s[N], t[N];
int n, m;
//区间加减可以使用前缀和和差分使得时间复杂度降低为O(n)
bool check(int m){
for (int i = 1; i <= n; i++) {
differ[i] = r[i] - r[i - 1];
}
for (int i = 1; i <= m; i++) {
differ[s[i]] -= d[i];
differ[t[i] + 1] += d[i];
}
for (int i = 1; i <= n; i++) {
differ[i] = differ[i] + differ[i - 1];
if (differ[i] < 0) return false;
}
return true;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%lld", r + i);
}
for (int i = 1; i <= m; i++) {
scanf("%lld%d%d", d + i, s + i, t + i);
}
if (check(m)) {
cout << 0 << endl;
return 0;
}
//二分再降低时间复杂度,log2m
//求的是最多能完成多少订单
int l = 0, r = m, mids = (l + r + 1) >> 1;
while (l < r) {
mids = (l + r + 1) >> 1;
if (check(mids)) {
l = mids;
}
else {
r = mids - 1;
}
}
cout << -1 << endl;
cout << r + 1 << endl;
return 0;
}