【题解】洛谷 P1083 借教室
2019-10-08 08:47:05来源:博客园 阅读 ()
【题解】洛谷 P1083 借教室
目录
- 题目
- 思路
- $Code$
题目
P1083 借教室
思路
线段树。需要的操作为区间修改,区间查询。维护每个区间的最小值就好。
$Code$
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define lson now<<1
#define rson now<<1|1
#define MAXN 1000001
#define rr register
#define min_(a,b) a>b?b:a
using namespace std;
int n,m;
struct Node{
int l,r,minn;
int lazy;
}tree[MAXN<<2];
inline void read(int &T) {
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
inline void write(int x) {
if(x<0) putchar('-'),write(-x);
else {
if(x/10) write(x/10);
putchar(x%10+'0');
}
}
void build(int l,int r,int now) {
tree[now].l=l,tree[now].r=r;
if(tree[now].l==tree[now].r) {
read(tree[now].minn);
return;
}
int mid=(tree[now].l+tree[now].r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
tree[now].minn=min_(tree[lson].minn,tree[rson].minn);
}
inline void pushdown(int now) {
if(tree[now].l==tree[now].r) return;
tree[lson].lazy+=tree[now].lazy;
tree[rson].lazy+=tree[now].lazy;
tree[lson].minn-=tree[now].lazy;
tree[rson].minn-=tree[now].lazy;
tree[now].lazy=0;
}
int query(int x,int y,int now) {
if(tree[now].l>=x&&tree[now].r<=y) {
return tree[now].minn;
}
if(tree[now].lazy) pushdown(now);
int mid=(tree[now].l+tree[now].r)>>1,minnn=0x7fffffff;
if(x<=mid) minnn=min(minnn,query(x,y,lson));
if(y>mid) minnn=min(minnn,query(x,y,rson));
return minnn;
}
void update(int x,int y,int k,int now) {
if(tree[now].l>=x&&tree[now].r<=y) {
tree[now].minn-=k;
tree[now].lazy+=k;
return;
}
if(tree[now].lazy) pushdown(now);
int mid=(tree[now].l+tree[now].r)>>1;
if(x<=mid) update(x,y,k,lson);
if(y>mid) update(x,y,k,rson);
tree[now].minn=min_(tree[lson].minn,tree[rson].minn);
}
int main() {
read(n),read(m);
build(1,n,1);
for(rr int i=1,x,y,k;i<=m;++i) {
read(k),read(x),read(y);
if(query(x,y,1)<k) {
puts("-1");
write(i);
return 0;
}else update(x,y,k,1);
}
puts("0");
return 0;
}
原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11627618.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:树-二叉树的基本概念
下一篇:长乐国庆集训Day3
- Unsolved --> Solved OJ思路题解 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- 洛谷P1907口算练习题 2020-03-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash