T2325.借教室
2023-08-05 13:33:04
发布于：浙江
1阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct dd{int d,s,t;} di[N];
int n,m,r[N],d[N];
int check(int x){
for(int i = 1;i <= n;i++){
d[i] = r[i] - r[i-1];
}
for(int i = 1;i <= x;i++){
int day = di[i].d, s = di[i].s, t = di[i].t;
d[s] -= day;d[t+1] += day;
}
int last = 0;
for(int i = 1;i <= n;i++){
last += d[i];
if(last < 0) return 0;
}
return 1;
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> r[i];
d[i] = r[i] - r[i-1];
}
for(int i = 1;i <= m;i++) cin >> di[i].d >> di[i].s >> di[i].t;
if(check(m)) cout << 0;
else{
cout << -1 << endl;
int ll = 1,rr = m;
while(ll < rr){
int mid = ll + rr >> 1;
if(check(mid)) ll = mid + 1;
else rr = mid;
}
cout << ll;
}
return 0;
}
这里空空如也
有帮助，赞一个