题解 | #[NOIP2012]借教室#
[NOIP2012]借教室
https://ac.nowcoder.com/acm/problem/16564
#include<stdio.h>
#include<limits.h>
#define Num 1000001
int element[Num];
int segment_tree[Num*4];
int lazy[Num*4];
void propagate(int node){
if(lazy[node]){
segment_tree[node*2]-=lazy[node];
segment_tree[node*2+1]-=lazy[node];
lazy[2*node]+=lazy[node];
lazy[2*node+1]+=lazy[node];
lazy[node]=0;
}
}
void build(int node,int start,int end){
if(start==end){
segment_tree[node]=element[start];
return;
}
int mid=(start+end)/2;
build(node*2,start,mid);
build(node*2+1,mid+1,end);
segment_tree[node]=segment_tree[node*2]<segment_tree[node*2+1]?segment_tree[node*2]:segment_tree[node*2+1];
}
int query(int node,int start,int end,int query_start,int query_end){
propagate(node);
if(query_start<=start&&query_end>=end)
return segment_tree[node];
int mid=(start+end)/2,answer=INT_MAX;
if(query_start<=mid){
int left_min=query(node*2,start,mid,query_start,query_end);
answer=left_min<answer?left_min:answer;
}
if(query_end>mid){
int right_min=query(node*2+1,mid+1,end,query_start,query_end);
answer=answer<right_min?answer:right_min;
}
return answer;
}
void update(int node,int start,int end,int update_start,int update_end,int value){
propagate(node);
if(start>=update_start&&end<=update_end){
segment_tree[node]-=value;
lazy[node]+=value;
return;
}
int mid=(start+end)/2;
if(update_start<=mid)
update(node*2,start,mid,update_start,update_end,value);
if(update_end>mid)
update(node*2+1,mid+1,end,update_start,update_end,value);
segment_tree[node]=segment_tree[node*2]<segment_tree[node*2+1]?segment_tree[node*2]:segment_tree[node*2+1];
}
int main(){
int num_elements,ele_opreations;
scanf("%d%d",&num_elements,&ele_opreations);
for(int i=1;i<=num_elements;i++)
scanf("%d",&element[i]);
build(1,1,num_elements);
for(int i=1;i<=ele_opreations;i++){
int decrement,start_range,end_range;
scanf("%d%d%d",&decrement,&start_range,&end_range);
if(decrement>query(1,1,num_elements,start_range,end_range)){
printf("-1\n%d\n",i);
return 0;
}
update(1,1,num_elements,start_range,end_range,decrement);
}
printf("0\n");
return 0;
}
美团公司氛围 2287人发布
投递联想等公司6个岗位 >