暴力上线段树即可,比二分+差分思路简单多了
线段树维护区间最小值然后和需要借教室的多少比较
再区间减即可
/*
线段树维护最小值
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define N 1000006
using namespace std;
int n,m;
int R[N];
int MIN[N*8];
int lazy[N*8];
void down(int x){
if(lazy[x]){
MIN[x*2]-=lazy[x];
MIN[x*2+1]-=lazy[x];
lazy[x*2]+=lazy[x];
lazy[x*2+1]+=lazy[x];
lazy[x]=0;
}
}
void buit(int bh,int l,int r)
{
if(l==r){
MIN[bh]=R[r];
return;
}
int mid=(l+r)/2;
buit(bh*2,l,mid);
buit(bh*2+1,mid+1,r);
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int ask(int bh,int l,int r,int cl,int cr)
{
down(bh);
if(cl<=l&&r<=cr){
return MIN[bh];
}
int mid=(l+r)/2,ans=INT_MAX;
if(cl<=mid) ans=min(ans,ask(bh*2,l,mid,cl,cr));
if(cr>mid) ans=min(ans,ask(bh*2+1,mid+1,r,cl,cr));
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
return ans;
}
void xg(int bh,int l,int r,int cl,int cr,int k)
{
down(bh);
if(cl<=l&&r<=cr){
MIN[bh]-=k;
lazy[bh]+=k;
return;
}
int mid=(l+r)/2;
if(cl<=mid) xg(bh*2,l,mid,cl,cr,k);
if(cr>mid) xg(bh*2+1,mid+1,r,cl,cr,k);
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&R[i]);
buit(1,1,n);
for(int i=1;i<=m;i++)
{
int d,s,t;
scanf("%d%d%d",&d,&s,&t);
int M=ask(1,1,n,s,t);
if(M>=d){
xg(1,1,n,s,t,d);
}else{
puts("-1");
cout<<i<<"\n";
return 0;
}
}
puts("0");
return 0;
}
不加O2优化的话,最后一个数据点会TLE
确实