记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 1ms 216.0 KiB
#2 Accepted 1ms 224.0 KiB
#3 Accepted 1ms 224.0 KiB
#4 Accepted 1ms 224.0 KiB
#5 Accepted 1ms 228.0 KiB
#6 Accepted 1ms 224.0 KiB
#7 Accepted 20ms 4.688 MiB
#8 Accepted 29ms 4.688 MiB
#9 Accepted 42ms 4.684 MiB
#10 Accepted 54ms 4.688 MiB
#11 Accepted 57ms 4.688 MiB
#12 Accepted 72ms 4.684 MiB
#13 Accepted 99ms 4.688 MiB
#14 Accepted 70ms 4.684 MiB
#15 Accepted 393ms 36.117 MiB
#16 Accepted 562ms 36.113 MiB
#17 Accepted 771ms 36.113 MiB
#18 Accepted 986ms 36.117 MiB
#19 Accepted 1217ms 36.113 MiB
#20 Accepted 1274ms 36.117 MiB

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0') f^=(c=='-'),c=getchar();
	while(c>'/') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
	return f?x:-x;
}
struct node{
	int l,r,tag,mn;
}stt[4000010];
int a[1000010];
inline void add(int k,int l,int r){
	stt[k].l=l;stt[k].r=r;
	if(l==r){
		stt[k].mn=a[l];
		return ;
	}
	int mid=(l+r)>>1;
    add(k<<1,l,mid);
    add(k<<1|1,mid+1,r);
    stt[k].mn=min(stt[k<<1|1].mn,stt[k<<1].mn);
}
inline void pushdown(int k){
	stt[k<<1].mn-=stt[k].tag;
	stt[k<<1|1].mn-=stt[k].tag;
	stt[k<<1].tag+=stt[k].tag;
	stt[k<<1|1].tag+=stt[k].tag;
	stt[k].tag=0;
	//stt[k].mn=min(stt[k<<1].mn,stt[k<<1|1].mn);
}
inline void mod(int k,int l,int r,int x){
	if(stt[k].l>=l&&stt[k].r<=r){
	  stt[k].mn-=x;
	  stt[k].tag+=x;
	  return ;
	}
	if(stt[k].tag)pushdown(k);
	int mid=(stt[k].l+stt[k].r)>>1;
	if(l<=mid)mod(k<<1,l,r,x);
	if(r>mid)mod(k<<1|1,l,r,x);
	stt[k].mn=min(stt[k<<1].mn,stt[k<<1|1].mn);
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read(); 
	}
	add(1,1,n);
	for(int i=1;i<=m;i++){
	 int d=read(),s=read(),t=read();
	 mod(1,s,t,d);
	 int q=stt[1].mn;//query(1,s,t);
	 //printf("%d\n",q);
	 if(q<0){
	   puts("-1");
	   printf("%d\n",i);
	   return 0;	
	 }	
	}
	puts("0");
    return 0;
}

信息

递交者
类型
递交
题目
P1042 借教室
比赛
随机真题赛第一轮(xhy&lfy讲题)
题目数据
下载
语言
C++
递交时间
2019-11-11 14:40:08
评测时间
2019-11-11 14:40:08
评测机
分数
100
总耗时
5662ms
峰值内存
36.117 MiB