由于刚开坑,所以就写点水题来撑门面吧。
题目链接




解题思路:
很简单,用一个线段树维护一下l到r的教室的最小值,时间复杂度
我们机房有很多大爷被卡时了,是因为他们把修改和判断分开写了,其实写在一个函数里可以过。



AC代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N,M;
int tree[3000010]={0};
int lazy[3000010]={0};
int a[1000010]={0};

void Pre_(int l,int r,int k)
{
    if(l==r)
    {
        tree[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Pre_(l,mid,k<<1);
    Pre_(mid+1,r,k<<1|1);
    tree[k]=min(tree[k<<1],tree[k<<1|1]);
    return;
}

void update(int k)
{
    lazy[k<<1]+=lazy[k];
    lazy[k<<1|1]+=lazy[k];
    tree[k<<1]-=lazy[k];
    tree[k<<1|1]-=lazy[k];
    lazy[k]=0;
    return;
}

int reduce(int al,int ar,int o,int k,int l,int r)
{
    if(al<=l && r<=ar)
    {
        lazy[k]+=o;
        tree[k]-=o;
        return tree[k];
    }
    int mid=(l+r)>>1;
    update(k);
    int g1=2e9,g2=2e9;
    if(al<=mid) g1=reduce(al,ar,o,k<<1,l,mid);
    if(ar>mid) g2=reduce(al,ar,o,k<<1|1,mid+1,r);
    tree[k]=min(tree[k<<1],tree[k<<1|1]);
    return min(g1,g2);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        scanf("%d",&a[i]);
    Pre_(1,N,1);
    for(int i=1;i<=M;i++)
    {
        int d,s,t;
        scanf("%d%d%d",&d,&s,&t);
        int g=reduce(s,t,d,1,1,N);
        if(g<0)
        {
            puts("-1");
            printf("%d\n",i);
            goto Break;
        }
    }
    puts("0");
    Break:;
    return 0;
}